晚會節目單
原題目鏈接
題目描述
小明要組織一臺晚會，總共準備了 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);}}
}
 C)
