题解 P3299 【[SDOI2013]保护出题人】

C20203030 · 2020-08-25 19:22:06 · 题解

一、题目

点此看题

二、解法

感觉这道题网上讲解不是特别清楚，我来补一发详细讲解吧，因为作者也是花了好久才搞懂。

首先把题目所求转化成形式化表达（其中s是生命值a的前缀和）：

是不是感觉难以优化，我们改换一种写法：

有点眼熟，可以转化为两个点(x[i]+id,s[i]),(jd,s[j-1])直线的斜率，对于后者，我们维护一个凸包，为什么要维护凸包呢？因为原问题在二维平面上是一个顶点到若干个点的最大斜率问题，看下图！ 可见在定点到凸包上点的斜率与凸包相切的时候斜率是最大的，当这样的点往前取和往后取答案都会减少，这种单调性给了我们快速解决问题的可能。补充一个问题：为什么凸包要维护单调递增的呢？我们还是结合图来分析，比如下面就是一个斜率单调递减的图，你仔细看看就知道中间的点永远不可能是答案。

接着单调性往下讲，我们可以考虑用二分来算答案，由于最优解是在中间的，我们二分出mid，比较它和mid-1跟定点连成的斜率谁是更大的，如果mid更大，那么往右边分，记录答案，否则往左边分。那么时间复杂度就做到了O(n\log n)，还有不懂请看代码。

#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);
}