NOIP1999提高组.拦截导弹

题目

P1020 [NOIP 1999 提高组] 导弹拦截

算法标签: 贪心, 二分, 动态规划, 树状数组

思路

因为洛谷对本题数据进行了加强, 因此需要更高效的做法, 第一问求的是最长不上升子序列, 可以使用树状数组维护前缀最大值求解, 第二问是贪心问题, 将每个导弹放到第一个大于等于该导弹高度的位置上, 如果不存在那么新创建一个系统, 可以发现每个系统的最后的高度是单调上升的, 因此可以二分求解, 算法时间复杂度$O(n\log n)$

不翻转原数组写法代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int tr[N];
vector<int> w, disc;

int lowbit(int x) {
   
    return x & -x;
}

void update(int u, int val) {
   
    for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], val);
}

int query(int u) {
   
    int res = 0;
    for (int i = u; i > 0; i -= lowbit(i)) res = max(res, tr[i]);
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int val;
    while (cin >> val) w.push_back(val);

    disc = w;
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());

    int res = 0;
    for (int i = 0; i < w.size(); ++i) {
   
        //因为树状数组下标从1开始 因此需要 + 1
        int idx = lower_bound(disc.begin(), disc.end(), w[i]) - disc.begin() + 1;
        idx = disc.size() - idx + 1;
        int curr = query(idx) + 1;
        update(idx, curr);
        res = max(res, curr);
    }

    vector<int> g;
    for (int num : w) {
   
        auto it = lower_bound(g.begin(), g.end(), num);
        if (it == g.end())  g.push_back(num);
        else *it = num;
    }

    cout << res << "\n" << g.size() << "\n";
    return 0;
}

翻转原数组写法代码

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int tr[N];
vector<int> w, disc;

int lowbit(int x) {
   
    return x & -x;
}

void update(int u, int val) {
   
    for (int i = u; i < N; i += lowbit(i)) tr[i] = max(tr[i], val);
}

int query(int u) {
   
    int res = 0;
    for (int i = u; i > 0; i -= lowbit(i)) res = max(res, tr[i]);
    return res;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int val;
    while (cin >> val) w.push_back(val);

    disc = w;
    sort(disc.begin(), disc.end());
    disc.erase(unique(disc.begin(), disc.end()), disc.end());

    int res = 0;
    
    reverse(w.begin(), w.end());
    for (int i = 0; i < w.size(); ++i) {
   
        //因为树状数组下标从1开始 因此需要 + 1
        int idx = lower_bound(disc.begin(), disc.end(), w[i]) - disc.begin() + 1;
        int curr = query(idx) + 1;
        update(idx, curr);
        res = max(res, curr);
    }

    reverse(w.begin(), w.end());
    vector<int> g;
    for (int num : w) {
   
        auto it = lower_bound(g.begin(), g.end(), num);
        if (it == g.end())  g.push_back(num);
        else *it = num;
    }

    cout << res << "\n" << g.size() << "\n";
    return 0;
}

*警示后人

因为树状数组的下标是从$1$开始的, 因此在进行下标映射的时候需要$+1$, 然后因为数据范围很大需要对数进行离散化