Circle of Monsters(贪心)

n个怪物围成一圈，每个怪物有自己的血量和爆炸伤害。
怪物在死后会对下一个怪物造成爆炸伤害，又死了又可以爆炸......
你每发子弹可以对怪物造成1点伤害，求杀死所有怪物的最小子弹数。

传送门

\(\color{Red}{---------------------华丽分割线w(ﾟДﾟ)w------------------------}\)

\(其实嘛，看到题目束手无策，但是看到数据范围会发现是个O(n)算法，那我们要开始找规律了。\)

\(首先还是想最坏情况，每个怪物都用子弹打，答案是所有怪物的血量和。\)

那么我们得出一个很沙雕但很重要的结论:尽可能利用爆炸伤害

\(爆炸伤害在最优时是每个怪物都炸下一个怪物，这样爆炸伤害和就是\)

\[\sum_{i=1}^{n-1}{min(本怪物爆炸伤害，下一个怪物血量)}+min(最后一个怪物爆炸伤害，第一怪物血量)
\]

但是这个伤害是打不出来的，因为我们需要一个起始点。

很明显我们取一个爆炸伤害对自己炸的血量最少的怪物为起点，这样其余所有爆炸伤害都可以打出来。

\(答案是sum(怪物血量和)-sum(爆炸伤害)+(爆炸贡献最小的一次爆炸伤害)\)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=300009;

ll t,n,a[maxn],b[maxn],c[maxn],explore,sumn,minn=1e18;

int main()

{

	cin>>t;

	while(t--)

	{

		minn=1e18,sumn=0,explore=0;

		int n;

		cin>>n;

		for(int i=1;i<=n;i++)

		{

			scanf("%lld%lld",&a[i],&b[i]);

			sumn+=a[i];

		}

		for(int i=1;i<=n-1;i++)

		{

			c[i]=min(b[i],a[i+1]),explore+=c[i];

			minn=min(minn,c[i]);

		}

		c[n]=min(b[n],a[1]);

		minn=min(minn,c[n]);

		explore+=c[n];

		cout<<sumn-explore+minn<<endl;

	}

}

巴特西

Circle of Monsters(贪心)

最新文章

热门文章