Circle of Monsters(贪心)

传送门

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

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

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

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

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

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

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

\(答案是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;
    }
}