懒惰的牛
问题描述
这是一个炎热的夏日。
懒洋洋的奶牛贝茜想将自己放置在田野中的某个位置,以便可以在短距离内尽可能多地吃到美味的草。
贝茜所在的田野中共有 N 片草地,我们可以将田野视作一个一维数轴。
第 i
片草地中包含 gi
单位的青草,位置坐标为 xi
。
不同草地的位置不同。
贝茜想选取田野中的某个点作为她的初始位置(可能是某片草地所在的点)。
只有一片草地与她的初始位置的距离不超过 K
时,贝茜才能吃到那片草地上的草。
如果贝茜选择最佳初始位置,请确定她可以吃到的青草最大数量。
输入格式
第一行包含两个整数 N
和 K
。
接下来 N
行,每行描述一片草地,包含两个整数 gi
和 xi
。
输出格式
输出如果贝茜选择最佳初始位置,则她可以吃到的青草最大数量。
数据范围
1≤N≤\(10^5\),
1≤gi≤10000,
0≤xi≤\(10^6\),
1≤K≤2×\(10^6\)
输入样例:
4 3
4 7
10 15
2 2
5 1
输出样例:
11
样例解释
最佳初始位置选择为 x=4,可以吃到 x=1,x=2,x=7 处的青草。
思路分析
完整代码
#include <bits/stdc++.h>
using namespace std;
int n, k;
typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII q[N];
#define x first
#define y second
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
{
scanf("%d%d", &q[i].y, &q[i].x);
}
sort(q, q + n);
int res = 0, sum = 0;
for(int i = 0, j = 0; i < n; i++)
{
sum += q[i].y;
while(q[i].x - q[j].x > 2 * k) sum -= q[j++].y;
res = max(res, sum);
}
cout << res << endl;
return 0;
}
标签:10,懒惰,int,贝茜,每日,位置,寒假,草地,sum
From: https://www.cnblogs.com/i-rong/p/17280966.html