这道题主要用差分.
差分
a数组:1 2 3 4 5
那么,用一个b数组, b[i] = a[i] - a[i - 1], 如b[3] = a[3] - a[2] = 1;
可知给b[i]做前缀和可以还原a[i]
那么如果cookiebus(忘记如何打删除线了手动删掉)要让a[2]到a[4]的数都加一,就只要b[2]++, b[4 + 1]--即可
How magic!
本题解法
用a数组模拟差分, 将每次的a[s]++, a[t+1]--然后前缀和统计
CODE
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], m;
signed main(){
cin >> n;
for(int i = 1; i <= n; i++){
int x, y;
scanf("%d %d", &x, &y);
a[x]++;
a[y + 1]--;
m = max(m, y);
}
int cnt = 0, ans = 0;
for(int i = 0; i <= m; i++){
cnt += a[i];
ans = max(ans, cnt);
}
cout << ans;
return 0;
}
结:今天培优卷太水了所以很闲就来水题
共 1 条回复
对呀，删除线怎么打啊？
我不会啊！