学习目标
贪心算法
[导弹拦截]
【算法分析】
首先考虑第一问，即序列中的最长不上升子序列。
令 g 为以 i 结尾的最长不上升子序列的值，那么可以枚举 g
1
~ gi−1，若 a
j
≤a
i
，则 g
i
=max(g
i
,g
j+1
)，否则 g
i
=max(g
i
,g
j
)。这么做显然是 O(n
2
) 的，需要进行优化。
若 a
i
小于等于 g 的最后一个元素，那么显然将 a 放至 g 的末尾。否则，将 a
i
替换掉 g 中第一个小于等于 a
i
的值。为什么这样做呢?假设 g
j
是 g 中第一个小于等于 a
i
的值，那么 g
j−1
一定大于 a
i
，若替换掉这一个，则肯定不划算(因为 g
j−1
会变小，但是答案没有变)，而替换掉 g
j
，则答案不变的同时 g
j
会变大，更加划算。
那么答案显然就是 g 数组的长度，可以用二分来查找「g中第一个小于等于a
i
的值」，复杂度(nlog
2
n)。
第二问见注释。
【参考代码】
#include <iostream>
using namespace std;
const int N = 5e5 + 10;
int a[N], x, n, dp[N], maxn;
int g[N], cnt;
int main() {
while (cin >> x) a[++n] = x;
g[0] = 5e4;
for (int i = 1; i <= n; i++) { //构造最长不上升子序列
if (a[i] <= g[cnt]) g[++cnt] = a[i]; //ai小于 g 中最后一个元素，将 ai 放末尾
else { //ai大于 g 中最后一个元素，找到 g 中第一个小于等于 ai 的值元素，交换
int l = 1, r = cnt;
while (l < r) {
int mid = (l + r) >> 1;
if (g[mid] < a[i]) r = mid;
else l = mid + 1;
}
g[l] = a[i];
}
}
cout << cnt << endl; // 答案为 最长不上升子序列 的长度
cnt = 0;
g[0] = -5e4;
for (int i = 1; i <= n; i++) { //gi表示第 i 个系统拦截的最低的导弹是什么,是一个上升子序列
if (a[i] > g[cnt]) g[++cnt] = a[i]; //ai 大于 g 中最后一个元素，需要新的导弹拦截系统
else { //ai 小于等于 g 中最后一个元素， 找到 g 中第一个大于等于 ai 的元素，交换
int l = 1, r = cnt;
while (l < r) {
int mid = (l + r) >> 1;
if (g[mid] >= a[i]) r = mid;
else l = mid + 1;
}
g[l] = a[i];
}
}
cout << cnt << endl;
return 0;
}
View Code
递推
[路径计数]
【算法分析】
状态数组 vis 对障碍物进行标记，遇到障碍物则方案数为 0。
递推式: f[i][j] = (f[i - 1][j] + f[i][j - 1]) % 100003;
【参考代码】
#include <iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
bool vis[N][N];
int main() {
int n, m;
cin >> n >> m;
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
vis[x][y] = true; //标记
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(!vis[i][j] ) f[i][j] = (f[i - 1][j] + f[i][j - 1]) % 100003;
if(i == 1 && j == 1) f[i][j] = 1;
}
}
cout << f[n][n];
return 0;
}
View Code
二分查找
STL容器栈
练习题[GITARA]
【算法分析】
建六个栈，代表每一根弦上的音调。
对于每次输入，如果栈顶比它小，就进栈，否则一直弹栈直到栈顶的数小于等于它。每次弹栈或进栈都要累计答案，最后输出即可。
【参考代码】
#include <iostream>
#include <stack>
using namespace std;
stack<int> st[7]; //六根弦的音调
int main() {
int n, p, ans = 0;
cin >> n >> p;
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
while(!st[x].empty() && st[x].top() > y){
ans++; //栈顶比当前的大，出栈
st[x].pop();
}
if(!st[x].empty()){ //栈里还有数
if(st[x].top() == y) continue;
ans++;
st[x].push(y);
} else { //栈空直接进栈
ans++;
st[x].push(y);
}
}
cout << ans;
return 0;
}
View Code
前缀和与差分数组
文件读取（重要）
[Sumy]
【算法分析】
对一条鱼来说，它的最优策略是:从小到大地吃掉其它所有的鱼。
注意到，由这个策略，可以发现鱼的存活与否满足单调性，即，如果一条鱼能活下来，比它大的鱼一定都能活下来，如果一条鱼活不下来，比它小的一定都活不下来。
注意边界情况:如果所有鱼的大小相同，则最大的鱼也没法吃掉其它所有的鱼，因此二分需要考虑所有鱼都无法活到最后的情况。
【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5 + 10;
struct node{
int w; //质量
int id; //编号
}a[N];
int n;
int vis[N];
bool cmp(node x, node y){
return x.w < y.w;
}
bool check(int x){ // 该鱼是否可以吃完其它所以的鱼
long long t = a[x].w;
for(int i = 1; i <= n; i++){
if(i == x) continue;
if(t <= a[i].w) return false;
t += a[i].w;
}
return true;
}
int main() {
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i].w;
a[i].id = i;
}
sort(a + 1,a + n + 1,cmp);
int l = 1, r = n, ans = n + 1; //当鱼的重量全部相等时，最大的鱼也不能吃掉所有的鱼，ans = n + 1
while(l <= r){
int mid = (l + r) >> 1;
if(check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
for(int i = 1; i <= n; i++){
if(i < ans) vis[a[i].id] = false;
else vis[a[i].id] = true;
}
for(int i = 1; i <= n; i++){
if(vis[i]) cout << 'T';
else cout << 'N';
}
return 0;
}
View Code
本节课作业讲解分析：
链接：https://pan.baidu.com/s/17LKht99FyUpobswJRkjlnQ?pwd=91n6
提取码：91n6
标签：11,int,U4,mid,C++,st,++,ans,include From： https://www.cnblogs.com/jayxuan/p/17937914