当前位置：首页 > ds >正文

NOIP1999提高组.拦截导弹

ds 2025/5/11 14:08:04

题目

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开始 因此需要 + 1int 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开始 因此需要 + 1int 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;
}