题目描述
给出$n$个位置和$k$个命令,每一次命令会给出$l$和$r$,你需要在$l$~$r$的每个位置加一,最后,请你给出$n$个位置的中间值,$n$一定为奇数。
算法:差分
此题为差分的模板题的改编。
如果我们暴力去给$l$~$r$的每一个位置手动加一,复杂度为$n^2$,一定会超时。
我们可以创建一个差分数组q[]
,$l$~$r$每一个位置加一,我们给q[l] ++
,这样,我们由差分数组还原到原数组时,$l$之后的位置都会多一,我们再给q[r + 1] --
,这样,$r + 1$之后的位置还是原来的值。
做完所有的命令后,我们先恢复出原数组,然后再对原数组进行排序,直接输出中间值即可。
思路
- 循环$k$次操作
- 输入$l$和$r$
q[l] ++
,q[r + 1] --
- 恢复原数组
- 排序
- 直接输出
q[(n + 1) >> 1]
注意点
C++
代码
#include <bits/stdc++.h>
using namespace std;
int q[1000010];
int main() {
int n, k;
cin >> n >> k;
for ( int i = 1; i <= k; i ++ ) {
int l, r;
cin >> l >> r;
q[l] ++;
q[r + 1] --;
}
for ( int i = 1; i <= n; i ++ ) q[i] += q[i - 1];
sort(q + 1, q + n + 1);
cout << q[(n + 1) >> 1];
return 0;
}
参考文献
题目链接
算法标签
差分