晚会节目单
原题目链接
题目描述
小明要组织一台晚会，总共准备了 n 个节目。然而晚会时间有限，他只能从中选择 m 个节目。
这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。
小明发现观众对于晚会的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。
小明为每个节目定义了一个好看值，请你帮助他选择出 m 个节目，满足他的要求。
输入描述
- 第一行包含两个整数
n, m，表示节目的总数和要选择的节目数。 - 第二行包含
n个整数，表示每个节目的好看值。
数据范围：
1 ≤ n ≤ 10^50 ≤ 节目的好看值 ≤ 10^5
输出描述
输出一行包含 m 个整数，为选出的节目的好看值，按选择顺序输出。
输入输出样例
输入
5 3
3 1 2 5 4
输出
3 5 4
样例说明
选择了第 1、4、5 个节目，得到的好看值序列是：3 5 4，在所有保持顺序的选择中是字典序最大的。
c++代码
#include<bits/stdc++.h>using namespace std;int n, m;
vector<int> arr, trees, tem;
unordered_map<int, vector<int>> mp;class node{
public:int val, num, index;
};void build(int p, int l, int r) {if (l == r) {trees[p] = arr[l];return;}int mid = (l + r) / 2;build(2 * p, l, mid);build(2 * p + 1, mid + 1, r);trees[p] = max(trees[2 * p], trees[2 * p + 1]);
}int ask(int p, int l, int r, int left, int right) {if (l >= left && r <= right) return trees[p];int mid = (l + r) / 2, a = 0, b = 0;if (mid >= left) a = ask(2 * p, l, mid, left, right);if (mid < right) b = ask(2 * p + 1, mid + 1, r, left, right);return max(a, b);
}void bfs() {node k, w;k.val = ask(1, 1, n, 1, n - m + 1), k.num = 0;queue<node> q;for (int x : mp[k.val]) {if (x > n - m + 1) break;k.index = x;q.push(k);}while(!q.empty()) {k = q.front(), q.pop();if (k.val < tem[k.num]) continue;else tem[k.num] = k.val;if (k.num == m - 1 || k.index + 1 > n || n - (m - k.num - 1) + 1 > n || k.index + 1 > n - (m - k.num - 1) + 1) continue;w.val = ask(1, 1, n, k.index + 1, n - (m - k.num - 1) + 1), w.num = k.num + 1;for (int x : mp[w.val]) {if (x <= k.index) continue;if (x > n - (m - k.num - 1) + 1) break;w.index = x, q.push(w);}}
}int main() {std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);cin >> n >> m;arr = vector<int>(n + 1), trees = vector<int>(4 * n), tem = vector<int>(m);for (int i = 1; i <= n; i++) cin >> arr[i], mp[arr[i]].push_back(i);build(1, 1, n);bfs();for (int i = 0; i < m; i++) {cout << tem[i];if (i != m - 1) cout << " ";}return 0;
}
实现思路
讲一下我的思路
首先我对这道题目的理解是，我们需要频繁查询区间最大值。
我们来看样例
5 3
3 1 2 5 4
实际上只有3 1 2可以选，因为选择5 4组成不了3个数
区间[1, 3]查询最值为3
实际上我们选了3后，只需要在3 的后面找两个数，那么4不可以选，因为凑不了两个
区间[2, 3]查询最值为5
同理区间[5, 5]查询最值为4
最终答案为3 5 4
然而，样例不会都这么简单，肯定有些分数是重复的，具体怎么解决重复。看下面解析。
算法步骤
我们刚刚得出，这个题目需要频繁地区间查询最值，我们选择线段树来解决，线段树查询一次最值只要O(logn)的时间。
读取输入
cin >> n >> m;
vector<int> arr(n + 1);
for (int i = 1; i <= n; i++) cin >> arr[i], mp[arr[i]].push_back(i);
构造线段树，编写查询方法
vector<int> trees(4 * n);//线段树定义void build(int p, int l, int r) {//递归建树if (l == r) {trees[p] = arr[l];return;}int mid = (l + r) / 2;build(2 * p, l, mid);build(2 * p + 1, mid + 1, r);trees[p] = max(trees[2 * p], trees[2 * p + 1]);
}int ask(int p, int l, int r, int left, int right) {//函数返回[left, right]里面的最大值if (l >= left && r <= right) return trees[p];int mid = (l + r) / 2, a = 0, b = 0;if (mid >= left) a = ask(2 * p, l, mid, left, right);if (mid < right) b = ask(2 * p + 1, mid + 1, r, left, right);return max(a, b);
}build(1, 1, n);
bfs广度优先
前面提到可能有多个局部最大值，我们必须要考虑每一个局部最大值，才能得出最终最大值。
为了快速得出数组里面有多少个局部最大值，我们用哈希表去存每一个值的下标是什么。
unordered_map<int, vector<int>> mp;
for (int i = 1; i <= n; i++) cin >> arr[i], mp[arr[i]].push_back(i);
然后我们开始bfs广度优先
class node{
public:int val, num, index;//val指当前节点的值，num指当前节点应该是第几个数，index表示数组里对应的下标。
};void bfs() {node k, w;k.val = ask(1, 1, n, 1, n - m + 1), k.num = 0;//第一个数的范围是[1, n - m + 1]，否则凑不齐m个数queue<node> q;for (int x : mp[k.val]) {if (x > n - m + 1) break;k.index = x;q.push(k);}while(!q.empty()) {k = q.front(), q.pop();if (k.val < tem[k.num]) continue;else tem[k.num] = k.val;if (k.num == m - 1 || k.index + 1 > n || n - (m - k.num - 1) + 1 > n || k.index + 1 > n - (m - k.num - 1) + 1) continue;//下一个数的范围是[k.index + 1, n - (m - k.num - 1) + 1]w.val = ask(1, 1, n, k.index + 1, n - (m - k.num - 1) + 1), w.num = k.num + 1;for (int x : mp[w.val]) {if (x <= k.index) continue;if (x > n - (m - k.num - 1) + 1) break;w.index = x, q.push(w);}}
}
