保护出题人「SDOI 2013」

题意

有n个关卡，每一关都会在僵尸队列的排头添加一只僵尸，同时排头与家的距离会发生变化。相邻僵尸之间的距离固定为(d)。

对于每一关，可以放置一颗任意攻击力的植物（每颗植物仅作用于当前关卡）。求攻击力总和最小值。

---

思路

显然(f[i]=max(frac{sum[i]-sum[j-1]}{x[i]+d*(i-j)}))，由于斜率没有单调性，所以二分凸包。

另注：题目的取整指的是四舍五入而不是向下取整，恶臭。

代码

#include <bits/stdc++.h>

using namespace std;

namespace StandardIO {

	template<typename T>inline void read (T &x) {
		x=0;T f=1;char c=getchar();
		for (; c<'0'||c>'9'; c=getchar()) if (c=='-') f=-1;
		for (; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
		x*=f;
	}

	template<typename T>inline void write (T x) {
		if (x<0) putchar('-'),x*=-1;
		if (x>=10) write(x/10);
		putchar(x%10+'0');
	}

}

using namespace StandardIO;

namespace Project {
	#define int long long
	
	const int N=100100;
	
	int n,d;
	int a[N],x[N];
	struct node {
		int x,y;
		node () {}
		node (int _x,int _y) : x(_x),y(_y) {}
	} Q[N];
	double ans;
	
	inline double slope (node x,node y) {
		return (double)(y.y-x.y)/(double)(y.x-x.x);
	}

	inline void MAIN () {
		read(n),read(d);
		for (register int i=1; i<=n; ++i) {
			read(a[i]),read(x[i]),a[i]+=a[i-1];
		}
		int tail=0;
		for (register int i=1; i<=n; ++i) {
			node now=node(d*i,a[i-1]);
			while (tail&&slope(Q[tail-1],Q[tail])>slope(Q[tail],now)) --tail;
			Q[++tail]=now;
			now=node(x[i]+d*i,a[i]);
			int l=1,r=tail,res,mid;
			while (l<=r) {
				mid=(l+r)>>1;
				if (slope(Q[mid],now)>slope(Q[mid-1],now)) l=mid+1,res=mid;
				else r=mid-1;
			}
			ans+=slope(now,Q[res]);
		}
		write((int)(ans+0.5));
	}
	
	#undef int
}

int main () {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	Project::MAIN();
}