题解 P3299 【[SDOI2013]保护出题人】
C20203030
2020-08-25 19:22:06
## 一、题目
[点此看题](https://www.luogu.com.cn/problem/P3299)
## 二、解法
感觉这道题网上讲解不是特别清楚，我来补一发详细讲解吧，因为作者也是花了好久才搞懂。
首先把题目所求转化成形式化表达（其中$s$是生命值$a$的前缀和）：
$$\sum_{i=1}^n\max_{j=1}^i \frac{s[i]-s[j-1]}{x[i]+(i-j)d}$$
是不是感觉难以优化，我们改换一种写法：
$$\sum_{i=1}^n\max_{j=1}^i \frac{s[i]-s[j-1]}{x[i]+id-jd}$$
有点眼熟，可以转化为两个点$(x[i]+id,s[i]),(jd,s[j-1])$直线的斜率，对于后者，我们维护一个凸包，为什么要维护凸包呢？因为原问题在二维平面上是一个顶点到若干个点的最大斜率问题，看下图！
可见在定点到凸包上点的斜率与凸包相切的时候斜率是最大的，当这样的点往前取和往后取答案都会减少，这种单调性给了我们快速解决问题的可能。补充一个问题：为什么凸包要维护单调递增的呢？我们还是结合图来分析，比如下面就是一个斜率单调递减的图，你仔细看看就知道中间的点永远不可能是答案。
接着单调性往下讲，我们可以考虑用二分来算答案，由于最优解是在中间的，我们二分出$mid$，比较它和$mid-1$跟定点连成的斜率谁是更大的，如果$mid$更大，那么往右边分，记录答案，否则往左边分。那么时间复杂度就做到了$O(n\log n)$，还有不懂请看代码。
```cpp
#include <cstdio>
const int M = 100005;
#define int long long
#define db double
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,d,top,s[M],a[M],b[M];db ans;
db slope(int x,int y)
{
return 1.0*(a[x-1]-a[y-1])/(x*d-y*d);
}
signed main()
{
n=read();d=read();
for(int i=1;i<=n;i++)
{
a[i]=a[i-1]+read();
b[i]=read();
}
s[0]=1;//防RE
for(int i=1;i<=n;i++)
{
while(top>1 && slope(s[top],s[top-1])>slope(i,s[top])) top--;
s[++top]=i;int t=1,l=1,r=top;
while(l<=r)
{
int mid=(l+r)>>1;
db x1=1.0*(a[i]-a[s[mid]-1])/(b[i]+(i-s[mid])*d);
db x2=1.0*(a[i]-a[s[mid-1]-1])/(b[i]+(i-s[mid-1])*d);
if(x1>=x2) l=mid+1,t=mid;
else r=mid-1;
}
ans+=1.0*(a[i]-a[s[t]-1])/(b[i]+(i-s[t])*d);
}
printf("%.0f\n",ans);
}
```