首先我们发现打的顺序一定是连续的，不然会浪费一次爆炸的机会，比如我打了x 不可能去打 x-1,因为这样x-1的爆炸用不到甚至有可能x-1不会被别的爆炸影响
比如我打了x 不可能直接打 x+2，因为这样x+1的位置最后一定要打但是他打完的爆炸就用不到了
因此我们枚举第一次打的位置，然后计算其他剩下的被i-1影响后的生命值剩下多少
#include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #include<map> #include<string> #include<vector> using namespace std; typedef long long ll; const int N=1e6+10; ll a[N],b[N],s[N]; ll res[N]; int main(){ int t; cin>>t; while(t--){ int n; cin>>n; int i; for(i=1;i<=n;i++){ scanf("%lld%lld",&a[i],&b[i]); } ll sum=0; for(i=1;i<=n;i++){ if(i==1){ res[i]=a[i]-b[n]; } else{ res[i]=a[i]-b[i-1]; } if(res[i]>0) sum+=res[i]; } ll ans=1e18; for(i=1;i<=n;i++){ ans=min(ans,sum-max(res[i],0ll)+a[i]); } cout<<ans<<endl; } return 0; }