快要 CSP-S2 了，複習一下一些演算法（弄文化課弄了好久了，很多東西都要忘了。。。
讀題
題目連結: Luogu P1020
資料是這樣的：389 207 155 300 299 170 158 65
推一推，我們發現，389 300 299 170 158 65是第一問的答案；在 155->300的時候，要使用另外一顆炮彈了，故最少應該配備兩套。
在草稿紙上面推一推，不難發現，這道題的兩小問，就是讓你求一個不上升序列長度和一個上升序列長度。
預備知識
在求這兩個東西之前，需要先學習STL中的兩個函式：lower_bound upper_bound。
其中， lower_bound 是求序列中第一個大於等於某個數的數；upper_bound 是求序列中第一個大於某個數的數。這兩個函式返回的是指標。
它們使用的前提是 序列是有序的。
以lower_bound為例，具體用法類似：
1
2
3
| int a[100];
lower_bound(a, a+len, x);
|
這一函式預設是求升序序列中符合條件的數，如果要改為降序序列，則需要一個 cmp 函式，這一點類似於 sort。比如：
1
2
3
| int a[100];
lower_bound(a, a+len, x, std::greater<int>());
|
解題
我的 AC 程式碼。
本題有兩種演算法，O(n)O(n)，O(nlogn)O(nlogn)。這裡只講後者。
不上升序列
我們用陣列d1當作棧來儲存它。
遍歷導彈高度，把棧頂元素和高度比較：
- 若 ai<=dlena_i <= d_len，此時aia_i是符合要求的，直接入棧。
- 若 ai>dlena_i > d_len，此時aia_i把棧內第一個小於它的覆蓋掉。這裡說一下，能夠覆蓋它是因為我們不需要再訪問它的值了。在測試資料中，此後幾次都會進行這一操作，如果僅僅取這幾個資料，最長不上升子序列長度仍然正確； 取所有資料，幾次操作之後，就會執行操作1，結果仍然正確。
上升序列
和不上升序列一樣，只不過把 upper_bound 改為了 lower_bound，因為會出現兩個相同高度的導彈的情況，這兩個導彈僅僅需要同一的炮彈去攔截。
程式碼
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| #include <algorithm>
#include <iostream>
using namespace std;
int ARR[100001];
int n = 0;
int d1[100001];
int c1 = 0;
int d2[100001];
int c2 = 0;
int main() {
while (cin >> ARR[n]) n++;
d1[0] = ARR[0];
d2[0] = ARR[0];
for (int i = 1; i < n; i++) {
if (ARR[i] <= d1[c1])
d1[++c1] = ARR[i];
else {
int j = upper_bound(d1, d1 + c1, ARR[i], greater<int>()) - d1;
d1[j] = ARR[i];
}
if (ARR[i] > d2[c2])
d2[++c2] = ARR[i];
else {
int j = lower_bound(d2, d2 + c2, ARR[i]) - d2;
d2[j] = ARR[i];
}
}
cout << c1 + 1 << endl << c2 + 1 << endl;
return 0;
}
|
結語
能力有限，如有疏漏，請諒解並補充，謝謝。
