OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SDOI2013】保护出题人

【题目描述】

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

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

僵尸从唯一一条笔直道路接近,你们需要在铭铭的房门前放置植物攻击僵尸,避免僵尸碰到房子。第一关,一只血量为a1点的僵尸从距离房子x1米处匀速接近,你们放置了攻击力为y1点/秒的植物进行防御;第二关,在上一关基础上,僵尸队列排头增加一只血量为a2点的僵尸,与后一只僵尸距离d米,从距离房子x2米处匀速接近,你们重新放置攻击力为y2点/秒的植物;……;第n关,僵尸队列共有n只僵尸,相邻两只僵尸距离d米,排头僵尸血量为an排第二的僵尸血量an-1,以此类推,排头僵尸从距离房子xn米处匀速接近,其余僵尸跟随排头僵尸同时接近,你们重新放置攻击力为yn点/秒的植物。

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

游戏得分取决于你们放置的植物攻击力的总和Σyi,和越小分数越高,为了追求分数上界,你们每关都要放置攻击力尽量小的植物。

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

【输入】

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

【输出】

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

【输入样例】

5 2

3 3

1 1

10 8

4 8

2 3

【输出样例】

7

【数据范围】

对于100%的数据, 1≤n≤10^5,1≤d≤10^12,1≤x≤ 10^12,1≤a≤10^12

【题解】

这道题理解题意很困难,很难想明白为什么要保护出题人。

嗯……

想明白了的话,就会发现每一天只考虑新加入的僵尸是不行的,因为排头僵尸和房子的距离也发生了变化。事实上,我们需要考虑从排头开始,连续打一串前缀僵尸需要的最小攻击力,把a[i]处理为前缀和,那么yi=max{(a[i]-a[j-1])/(x[i]+d*(i-j))},j≤i。根据某神犇的话,这种式子很像斜率的计算公式((yi-yj)/(xi-xj)的形式),所以先化简、统一下标,则所求式子为(x[i]+d*i,a[i]),(d*j,a[j-1])两点间的斜率。那么问题就转化成了n次询问,每次询问一个点(x[i]+d*i,a[i]),找出其和(d*j,a[j-1])的斜率的最大值(j≤i)。

但如果每次枚举的话,时间复杂度O(n^2),TLE无误,所以我们需要一点单调性。由于d*j和a[j-1]都是单调递增的,而x[i]+d*i>d*j,a[i]>a[j-1],所以符合条件的点一定在(d*j,a[j-1])的下凸壳中,用一个单调栈来维护。

求出下凸壳后,明显满足条件的点有且仅有一个,这个点两侧的点斜率都是单调递减的。换句话说,询问点和下凸壳上的点的斜率函数是单峰的,可以考虑整数三分来求解。但是由于我太弱,整数三分肯定跪QAQ所以根据某位神犇的代码,采用二分来找这个点。每次二分的时候,如果发现mid点的斜率比mid-1的斜率大,就把当前的mid记录下来,最后记录的最大值就是所求点了。

【代码】

精度绰绰有余,时间复杂度O(nlogn)。

http://paste.ubuntu.com/8036201/

评论

© OI技术宅 | Powered by LOFTER