题目链接
易得第(i)关的最小攻击力为(max_{j=1}^ifrac{sum[i]-sum[j-1]}{x+d*(i-j)})
十分像一个斜率式，于是看作一个点(P(x+d*i,sum[i]))和点(Q(d*j,sum[j-1]))的斜率
于是就是求当前(i)的点(P)和之前的所有点(Q)的最大斜率，显然有最大斜率的点在凸包上而且有单峰。
于是用单调队列维护凸包，在凸包上三分斜率最大值。
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int MAXN = 100010;
inline ll read(){
ll s = 0;
int w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }
while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
int n, top;
ll d;
ll a[MAXN], x[MAXN], sum[MAXN];
int st[MAXN];
double k(int i, int j){
return ((double)sum[i - 1] - sum[j - 1]) / (i * d - j * d);
}
double calc(int i, int j){
return ((double)sum[i] - sum[j - 1]) / (x[i] + d * (i - j));
}
double ans;
int main(){
n = read(); d = read();
for(int i = 1; i <= n; ++i){
a[i] = read(); x[i] = read();
sum[i] = sum[i - 1] + a[i];
}
for(int i = 1; i <= n; ++i){
while(top > 1 && k(st[top - 1], st[top]) > k(st[top - 1], i)) --top;
st[++top] = i;
int l = 1, r = top, mid1, mid2, p;
while(l != r){
p = (r - l + 1) / 3;
mid1 = l + p - 1;
mid2 = l + p + p - 1;
if(mid1 == mid2) break;
if(calc(i, st[mid1]) < calc(i, st[mid2])) l = mid1 + 1;
else r = mid2 - 1;
}
ans += max(calc(i, st[l]), calc(i, st[r]));
}
printf("%.0lf
", ans);
return 0;
}