Circle of Monsters[*1600][暴力][构造]

Problem - C - Codeforces

有 \(N\) 头怪兽，他们围成一个环，顺时针编号 \(1,2,3,4,\dots ,N\) 每一头怪兽都有 2 个属性，一个是它的生命值 \(a_i\)，第二个是它的爆炸值 \(b_i\)。

你有一把手枪，每开一枪可以对你选定的一只怪兽造成 \(1\) 伤害（使其生命值 \(-1\)）

当一个怪兽死后（生命值 \(\leq 0\)），它会发生爆炸，并对下一个怪兽（假设当前怪兽为编号 \(i\)，则下一个为 \(i+1\)。如果 \(i=n\)，则下一个为 \(1\) 号）
造成 \(b_i\) 点伤害。如果下一个怪兽已经死了，则没有事发生。如果下一个怪兽被炸死了，那么他也会爆炸，并对下下个怪兽造成伤害。以此类推。

询问你最少开几枪可以杀死所有怪兽。

每个测试点多组数据，\(\sum N\leq 3\times 10^5\)，\(a_i,b_i\leq 10^{12}\)

思路

因为前面做了一道树的题用的贡献做的感觉很妙

所以这个题我也用贡献考虑的

因为要手动打爆一个怪兽

那么前面那个怪兽爆炸的值就扑空了

那么我们要让扑空的爆炸值最小

每一个怪兽爆炸的贡献是\(Min\)(这个怪兽爆炸所产生的伤害，下一个怪兽的血条)

我们找到最小的贡献，然后让他扑空以后，加上每一头怪兽需要补充的伤害就可以了

这道题思路口胡用了2分钟

敲码用了3分钟

然后交上去WA8了哈哈哈，本来打算去看题解了

然后发现是数组开小了，把数组开到3e5然后居然AC了

五分钟AC了1600的题后的反应是这题真水哈哈

key code

const int N=3e5+10;
int n,m;
PII a[N];
void solve(){
	//try it again.
	cin>>n;
	up(1,n){
		int x,y;
		cin>>x>>y;
		a[o]={x,y};
	}
	a[0]=a[n];
	int minn=INF;
	int sum=0;
	up(1,n){
		minn=min(min(a[o-1].se,a[o].fi),minn);
	}
	up(1,n){
		sum+=max(0ll,a[o].fi-a[o-1].se);
	}
	cout<<sum+minn<<endl;
}