题面
打怪时，显然从右往左打最优
答案显然具有单调性，考虑二分
然后看一下怎么算溅射伤害
设前面几枪打的位置构成序列{a_n}
于是x处溅射伤害$=\sum_{i=1}^n p-(x-a_i)^2=\sum_{i=1}^n p-x^2+2\times a_i\times x-a_i^2=n\times (p-x^2)+2\times x\times \sum a_i-\sum a_i^2$
于是维护个数，和，平方和即可
注意一下，超过最大距离要删除1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
using namespace std;
typedef long long ll;
ll p, k, n;
ll a[1000010], tot[1000010];
struct data {
ll cnt, cnti, cnti2;
inline void clear() {
cnt = cnti = cnti2 = 0;
}
inline void add(ll i, ll k) {
cnt += k;
cnti += k * i;
cnti2 += k * i * i;
}
inline ll get(ll i) {
return (p - i * i) * cnt + 2 * cnti * i - cnti2;
}
} d;
inline ll check() {
ll maxdis = 0, sum = 0;
d.clear();
for(; maxdis <= n && maxdis * maxdis <= p; maxdis++);
// printf("%lld %lld\n", p, maxdis);
for(ll i = n; i > 0; i--) {
if(i + maxdis <= n) d.add(i + maxdis, -tot[i + maxdis]);
ll rest = a[i] - d.get(i);
if(rest < 0) tot[i] = 0;
else tot[i] = rest / p + 1;
d.add(i, tot[i]);
sum += tot[i];
}
// for(int i = 1; i <= n; i++) printf("%lld ", tot[i]);
// puts("");
return sum <= k;
}
int main() {
scanf("%lld%lld", &n, &k);
for(ll i = 1; i <= n; i++) scanf("%lld", a + i);
ll ans, l = 1, r = 3e11;
while(l <= r) {
p = (l + r) >> 1;
if(check()) ans = p, r = p - 1;
else l = p + 1;
}
return cout << ans << endl, 0;
}