題目鏈接：點擊查看

題目大意：給出一個長度為 n 的數列，再給出 m 次詢問，每次詢問給出一個閾值 x ，問最少將數列分割成多少段，可以使得每一段的總和都不超過 x，無解的話輸出?Impossible

題目分析：首先單獨討論一下無解的情況，因為數列總是可以被分成 n 段，也就是每個元素獨立一段，這樣的話如果閾值小于最大值的話顯然是無解的

如果不考慮時間復雜度的話，不難想到一個 n * m 的做法，就是對于每個詢問，都掃一遍數列，然后貪心求解

考慮優化，首先 m 個詢問肯定是無法優化的，對于掃一遍數列的時間復雜度 O( n )，考慮優化，因為數列中的每個元素都是正整數，所以維護的前綴和一定是遞增的，所以對于每段區間可以進行二分去劃分，比如初始時未經過劃分的總區間為 [ 1 , n ] ，設閾值為 x ，我們可以二分出一個最大的 pos，使得 sum[ pos ] - sum[ 0 ] <= x，這樣可以直接將區間 [ 1 , pos ] 劃分為第一段，然后再去給區間 [ pos + 1 , n ] 進行劃分，這樣做的時間復雜度最壞還是會退化為 O( n ) 的，但考慮利用數組記憶化一下，因為題目中約束了每個詢問的閾值一定是小于等于 1e6 的，好像也是在暗示我們要記憶化一樣，然后時間復雜度就不太會計算了，暫且當做 O( 能過 ) 吧

代碼：
?

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #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<cassert> #include<bitset> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;int n,m,mmax,sum[N],ans[N];int solve(int x) {if(ans[x])return ans[x];int last=1;ans[x]=0;while(last<=n){ans[x]++;int l=last,r=n,ans=-1;while(l<=r){int mid=l+r>>1;if(sum[mid]-sum[last-1]<=x){l=mid+1;ans=mid;}elser=mid-1;}last=ans+1;}return ans[x]; }int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);scanf("%d",&n);for(int i=1;i<=n;i++){int num;scanf("%d",&num);mmax=max(mmax,num);sum[i]=sum[i-1]+num;}scanf("%d",&m);while(m--){int x;scanf("%d",&x);if(x<mmax)puts("Impossible");elseprintf("%d\n",solve(x));}return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - High Load Database(二分+记忆化)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。