露西亚的训练计划
设低，中，高三种强度的训练编号分别为 1，2，3。
乱搞DP。设 dp i,j 表示训练的第 i 天选择 j 强度的训练方案得到的最大训练效果。则转移方程为：
dp i,j = max(dp i-1,1 , dp i-1, 2 , dp i-1, 3) (j ≠ 3)
dp i,j = dp i-1,1 (j = 3)
搞定。
摧毁车厢
外加手写高精。
终末祈愿
一眼就得是二分。
二分半径，考虑如何check。
显然，对于每次攻击，攻击的区间一定从最左边开始是最优的。举个栗子例子：
现在有3只感染体，分别在1 ， 10， 100 的位置，且生命值均为1，单次攻击区间长度为20，伤害为1。
那么第一次攻击一定是攻击（1，20）的位置，因为最左边的感染体位置为1，那么攻击区间再向左偏移就没有意义了，还不如多向后边攻击一下。接下来确定单次攻击在数组中的下标范围。这里数据比较水，枚举每个点进行二分也卡得过去，但是正解是用尺取法。最后的模拟用前缀和作差，统计出半径为d时需要的最小次数，最后与m作对比即可。
std:
#include<bits/stdc++.h>
#define int long long
#define File(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
using namespace std;
int read(){
int sum = 0, f = 1;
char ch = getchar();
for(;!isdigit(ch);ch = getchar()) if(ch == '-') f = -1;
for(;isdigit(ch);ch = getchar()) sum = (sum << 3) + (sum << 1) + (ch ^ 48);
return sum * f;
}
void write(int x){
if(x < 0) putchar('-'), x = -x;
if(x > 9) write(x / 10);
putchar('0' + x % 10);
return;
}
const int N = 1e6 + 10;
int n, m, k, f[N], c[N];
struct node{
int x, h;
}a[N], target[N];
bool cmp(node x, node y){
return x.x < y.x;
}
bool check(int d){
memset(f, 0, sizeof(f));
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; ++ i) a[i] = target[i];
a[n + 1].x = 0x3f3f3f3f3f3f;
int l, r = 1;
for(l = 1; l <= n; ++ l){
while(r <= n && a[r + 1].x - a[l].x <= 2 * d) ++ r;
f[l] = r;
}
int t = 0, s = 0;
for(int i = 1; i <= n; ++ i){
t += c[i];
a[i].h += t;
if(a[i].h <= 0) continue;
int p = (a[i].h + k - 1) / k;
s += p;
t -= p * k;
c[i] += -p * k;
c[f[i] + 1] += p * k;
}
return s <= m;
}
signed main(){
n = read(), m = read(), k = read();
for(int i = 1; i <= n; ++ i){
target[i].x = read();
target[i].h = read();
}
sort(target + 1, target + n + 1, cmp);
target[n + 1].x = 0x3f3f3f3f3f;
int l = 0, r = 1e9, mid;
while(l + 1 < r){
mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid;
}
if(check(l)) write(l);
else write(r);
return 0;
}不明数据聚集体：
略，机房讲。
。. ���,�