題目鏈接：點擊查看

題目大意：給出n個城市，其編號分別為1~n，其之間首尾相連組成一個環(huán)形，每次經(jīng)過一個城市將獲得ai的錢，每次離開一個城市將花費bi的錢，要求選擇一個城市作為起點，然后順時針走完n個城市，并且保證路程中的錢數(shù)不能小于0

題目分析：這個題目因為說到了一點總的n不大于1e6，那完全可以暴力，一層枚舉起點，一層進行前綴和判斷是否符合條件，如果符合條件就輸出該序號，如果不符合條件繼續(xù)查找，雖然看上去是n*n的復(fù)雜度，其實有了剪枝實際上會小很多，但是我們一開始做這個題的時候想用二分，如果滿足條件就往左區(qū)間尋找，如果不滿足條件就往右區(qū)間查找，這樣能保證查出來的答案需要一定是最小的，但是卻忽略了很重要的一點，如果有10個點，中點是5，如果5不滿足條件，根據(jù)我設(shè)置的二分會向右邊查找，但此時答案如果是城市2，那么就搜索不到答案了，所以這個題目不能用二分。。當(dāng)時比賽的時候人真的傻了，一直在這里糾結(jié)，還以為自己寫的二分沒有任何問題。。還是需要練練暴力的題目，會了算法卻不會了最簡單的暴力，直接上代碼吧，大水題：

#include<iostream> #include<cstdio> #include<vector> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,m;int a[N];bool check(int x) {LL sum=m;for(int i=1;i<=n;i++){sum+=a[x];if(sum<0)return false;x++;if(x==n+1)x=1;}return true; }int main() {int w;cin>>w;while(w--){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",a+i);LL sum=m;for(int i=1;i<=n;i++){int num;scanf("%d",&num);a[i]-=num;sum+=a[i];}if(sum<0){printf("-1\n");continue;}int i;for(i=1;i<=n;i++)if(check(i))break;printf("%d\n",i);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HihoCoder - 1831 - 80 Days(暴力)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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