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的参赛选手，你们能保护出题人么？

输入输出格式

输入格式：

第一行两个空格隔开的正整数\(n\)和\(d\)，分别表示关数和相邻僵尸间的距离。

接下来\(n\)行每行两个空格隔开的正整数，第\(i + 1\)行为\(A_i\)和 \(X_i\)，分别表示相比上一关在僵尸队列排头增加血量为\(A_i\) 点的僵尸，排头僵尸从距离房子\(X_i\)米处开始接近。

输出格式：

一个数，\(n\)关植物攻击力的最小总和 ，保留到整数。

说明

对于\(100\%\)的数据， \(1\le n\le 10^5，1\le d\le 10^{12},1\le x\le 10^{12},1\le a\le10^{12}\)

---

我自己只有一个naive的想法

整体二分，然后对在里面搞凸包弄一弄，感觉是可以做的，但是懒得写。

正解

设\(n\)个僵尸的前缀血量和为\(hp_i\)，第\(i\)个僵尸为开头时距离房间为\(X_i\)

\[ \sum_{p=1}^n\max_{i=1}^p\frac{hp_p-hp_{i-1}}{X_p+p\times d-i\times d} \]

然后对前\(i\)个僵尸组成的波，维护点集\((i\times d,hp_i-1)\)的一个凸壳

然后每次询问\((hp_p,X_i+p\times d)\)与凸壳上一个点的最大斜率，直接三分就可以了

关于整数域上的三分，和二分一样写其实就可以，而且更快

---

Code:

#include 
    
     #include 
     
      const int N=1e5+10;#define mp(a,b) std::make_pair(a,b)std::pair 
      
        yuu[N];int s[N],tot,n;double hp[N];double slope(int a,int b){    return (yuu[b].second-yuu[a].second)/(yuu[b].first-yuu[a].first);}void ins(double x,double y){    yuu[++n]=mp(x,y);    while(tot>1&&slope(n,s[tot])
       
        >1;        if(slope(0,s[mid])
       
      
     
    

---

2019.2.14