【TCO2016 Round 1B Div1 1000】SettingShield

  考场上猜是三分然而并没有调好...

  三分需要用多少次特殊的盾牌，花费关于这个值是一个单峰函数。然后直接做就好了。

#include <bits/stdc++.h>
using namespace std;
static const int maxn=100010;
static const long long inf=~0ull>>1;

struct Segment
{
	int left,right;
}S[maxn];

int prot[maxn];
int f[maxn];
int _n,_h,_t;

long long Solve(int v)
{
	long long rest=0,cost=0;
	memset(f,0,sizeof(f));
	for (int i=1,p=0,r=0;i<=_n;i++)
	{
		rest-=f[i];
		while (p<_h && S[p+1].left<=i) r=max(r,S[++p].right);
		if (rest+v<prot[i]) {
			int ad=prot[i]-rest-v;
			f[r+1]+=ad;
			cost+=ad;
			rest+=ad;
		}
	}
	return cost+(long long)v*_t;
}

bool scmp(const Segment &a,const Segment &b) {return a.left<b.left || (a.left==b.left && a.right>b.right);}

class SettingShield {
public:	
	long long getOptimalCost(int n, int h, int t, vector <int> val0, vector <int> a, vector <int> b, vector <int> m) {
		_n=n;_h=h;_t=t;
		prot[1] = val0[0];
		for (int i=2;i<=n;i++)
		prot[i] = ((long long)a[0] * prot[i-1] + b[0]) % m[0];
		S[1].left = val0[1];
		S[1].right = val0[2];
		for (int i=2;i<=h;i++)
		{
			S[i].left = min(n-1ll, ((long long)a[1] * S[i-1].left + b[1]) % m[1]);
			int dist = S[i-1].right - S[i-1].left;
			S[i].right = min(n-1ll, S[i].left + ((long long)a[2] * dist + b[2]) % m[2]);
		}
		for (int i=1;i<=h;i++) S[i].left++,S[i].right++;
		sort(S+1,S+h+1,scmp);
		int ansl=0,ansr=0;
		for (int i=1,p=0,r=0;i<=n;i++)
		{
			while (p<h && S[p+1].left<=i) r=max(r,S[++p].right);
			if (S[p].left>i || r<i) ansl=max(ansl,prot[i]);
			ansr=max(ansr,prot[i]);
		}
		while (ansr-ansl>5)
		{
			int mid=(ansr-ansl)/3;
			if (Solve(ansl+mid)<Solve(ansr-mid)) ansr=ansr-mid;else ansl=ansl+mid;
		}
		long long ans=1e12;
		for (int i=ansl;i<=ansr;i++) ans=min(ans,Solve(i));
		return ans;
	}
};