洛谷P3299 [SDOI2013]保护出题人题解

题目链接：P3299 [SDOI2013]保护出题人

题意：出题人铭铭认为给SDOI2012出题太可怕了，因为总要被骂，于是他又给SDOI2013出题了。

参加SDOI2012的小朋友们释放出大量的僵尸，企图攻击铭铭的家。而你作为SDOI2013的参赛者，你需要保护出题人铭铭。

僵尸从唯一一条笔直道路接近，你们需要在铭铭的房门前放置植物攻击僵尸，避免僵尸碰到房子。

第一关，一只血量为 \(a_1\) 点的墦尸从距离房子 \(x_1\) 米处速接近，你们放置了攻击力为 \(y_1\) 点/秒的植物进行防御；第二关，在上一关基础上，僵尸队列排头增加一只血量为 \(a_2\) 点的僵尸，与后一只僵尸距离 \(d\) 米，从距离房 \(x_2\) 米处匀速接近，你们重新放置攻击力为 \(y_2\) 点/秒的植物；……；第 \(n\) 关，僵尸队列共有 \(n\) 只僵尸，相邻两只僵尸距离 \(d\) 米，排头僵尸血量 \(a_n\) 点，排第二的僵尸血量 \(a_{n-1}\) ，以此类推，排头僵尸从距离房子 \(x_n\) 米处匀速接近，其余僵尸跟随排头同时接近，你们重新放置攻击力为 \(y_n\) 点/秒的植物。

每只僵尸直线移动速度均为 \(1\) 米/秒，由于植物射击速度远大于僵尸移动速度，可忽略植物子弹在空中的时间。所有僵尸同时出现并接近，因此当一只僵尸死亡后，下一只僵尸立刻开始受到植物子弹的伤害。

游戏得分取决于你们放置的植物攻击力的总和 \(\sum \limits _{i=1} ^{n} y_i\)，和越小分数越高，为了追求分数上界，你们每关都要放置攻击力尽量小的植物。

作为SDOI2013的参赛选手，你们能保护出题人么？

对于第 \(i\) 轮的第 \(j\) 只僵尸，打死它的充要条件为它前面的僵尸全部被打死

它需要走过的距离为 \(x_i+d\times (i-j+1)\) ，则最小的攻击为 \[ \dfrac{\sum_{k=j}^{i}a_k}{x_i+d\times(i-j+1)} \] 则第 \(i\) 轮进攻的最小攻击 \[ y_i = \max\left(\dfrac{S_i-S_{j-1}}{x_i+d\times(i-j+1)}\right) \] 其中，\(S_i = \sum_{k=1}^{i} a_k\)

稍微观察一下式子，可以发现 \[ y_i = \max\left(\dfrac{S_i-S_{j-1}}{(x_i+d\times i)-d\times(j-1)}\right) \] 即点 \((x_i+d\times i,i)\) 和 \((d\times(j-1),j-1)\) 的直线斜率

而前者在仅与 \(i\) 有关，可以看作定点；后者则与 \(i\) 无关，仅与每只僵尸有关

考虑对 \((d\times(j-1),j-1)\) 维护一个下凸壳

每一轮二分一个点使得其和定点所成直线斜率最大

把这些斜率加起来就是答案了

注意本题是四舍五入，而不是向下取整

时间复杂度 \(O(n\log n)\)

代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)
int n;
struct vct
{
    int x,y;
    vct operator-(const vct o)const
    {
        return {x-o.x,y-o.y};
    }
}stk[N];
int d,sum[N],top;
double cross(vct a,vct b)
{
    return a.x*b.y-a.y*b.x;
}
double slope(vct a,vct b)
{
    return 1.0*(a.y-b.y)/(a.x-b.x);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> d;
    stk[0]={0,0};
    double res=0;
    for(int i=1,a,x; i<=n; i++)
    {
        cin >> a >> x;
        sum[i]=sum[i-1]+a;
        vct tmp={i*d,sum[i-1]};
        while(top&&cross(stk[top]-stk[top-1],tmp-stk[top])<=0)
            --top;
        stk[++top]=tmp;
        tmp={x+i*d,sum[i]};
        int l=1,r=top;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(slope(stk[mid],tmp)>slope(stk[mid-1],tmp))
                l=mid;
            else r=mid-1;
        }
        res+=slope(stk[l],tmp);
    }
    cout << fixed << setprecision(0);
    cout << res << endl;
    return 0;
}