題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)有順序的環(huán)形敵人序列，每個(gè)敵人有兩個(gè)屬性，分別記為 a 和 b ，a 為 該敵人的血量，需要相應(yīng)的子彈數(shù)量才能擊敗，當(dāng)敵人 i 被擊敗后，他會(huì)爆炸，對(duì)第 i + 1 名敵人造成 b[ i ] 的傷害，問至少需要用多少子彈才能將敵人都消滅

題目分析：因?yàn)?b 都是大于 0 的數(shù)，所以最優(yōu)解肯定是先挑選一個(gè)敵人開始，然后按照順序依次擊殺，不難看出這樣是最優(yōu)的，那么找出第一個(gè)擊殺的敵人成了這個(gè)題的突破口，我的第一反應(yīng)是找到 a[ i ] 的最小值入手，但不幸的是這樣做并不對(duì)，后來看到了數(shù)據(jù)范圍給了提示，就恍然大悟了，想一下為什么 a 和 b 的數(shù)值都給到了 1e12 ，而不是正常的 1e9 或 1e5 呢，顯然是需要進(jìn)行某種操作，而不能超過 1e18 ，這相差了不到?1e6?的量級(jí)恰好就和敵人的數(shù)量 n 對(duì)應(yīng)了起來，所以數(shù)據(jù)范圍提示我們需要維護(hù)一個(gè)前綴和，這樣一想我們因?yàn)橹皇堑谝粋€(gè)敵人的選擇不一樣，所以可以一層循環(huán)枚舉起點(diǎn)然后維護(hù)最小值作為答案

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=3e5+100;LL a[N],b[N],c[N];int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld",a+i,b+i);LL sum=0;for(int i=1;i<=n;i++)//敵人受到爆炸后的剩余血量記為數(shù)組 c {if(i==1)c[i]=a[1]-b[n];elsec[i]=a[i]-b[i-1];if(c[i]<0)c[i]=0;sum+=c[i];}LL ans=0x3f3f3f3f3f3f3f3f;for(int i=1;i<=n;i++)ans=min(ans,sum-c[i]+a[i]);printf("%lld\n",ans);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 1334C Circle of Monsters(贪心)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。