G 空调遥控
题目大意：
给出n个人，每个人有一个温度适应区间[k-a[i],k+a[i]],k表示当前室温，要使其小于等于p,问室温设置那个温度点可以使更多的人适应。
思路：
我们逆向思考一下，那么对于每一个人室温适应的区间就是[a[i]-p,a[i]+p]. 那么考虑差分数组，最后再用一遍前缀和累加取最大值就行了。 注意下a[i]-p可能为负数，记得与0处理一下！
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2e6 + 10;
int n, p, a[N], d[N], ans;
int main()
{
scanf("%d%d", &n, &p);
for(int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
d[max(a[i] - p, 0)] += 1, d[a[i] + p + 1] -= 1;
}
for(int i = 1; i <= n; i++) d[i] += d[i - 1];
for(int i = 1; i <= n; i++) ans = max(ans, d[i]);
printf("%d\n", ans);
return 0;
}
查看9道真题和解析