題解 導彈攔截

快要 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為例，具體用法類似：

int a[100];
// ...
lower_bound(a, a+len, x); // 前兩個引數傳入的都是指標

這一函式預設是求升序序列中符合條件的數，如果要改為降序序列，則需要一個 cmp 函式，這一點類似於 sort。比如：

int a[100];
// ...
lower_bound(a, a+len, x, std::greater<int>()); // 前兩個引數傳入的都是指標

解題

我的 AC 程式碼。

本題有兩種演算法，O(n)，O(nlogn)。這裡只講後者。

不上升序列

我們用陣列d1當作棧來儲存它。

遍歷導彈高度，把棧頂元素和高度比較：

1. 若 a_i <  = d_len，此時a_i是符合要求的，直接入棧。
2. 若 a_i > d_len，此時a_i把棧內第一個小於它的覆蓋掉。這裡說一下，能夠覆蓋它是因為我們不需要再訪問它的值了。在測試資料中，此後幾次都會進行這一操作，如果僅僅取這幾個資料，最長不上升子序列長度仍然正確； 取所有資料，幾次操作之後，就會執行操作1，結果仍然正確。

上升序列

和不上升序列一樣，只不過把 upper_bound 改為了 lower_bound，因為會出現兩個相同高度的導彈的情況，這兩個導彈僅僅需要同一的炮彈去攔截。

程式碼

#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;
}

結語

能力有限，如有疏漏，請諒解並補充，謝謝。