正題

---

大意

每個人有兩個值gigi和hihi，要求將序列分解成連續的幾個序列。要求每個序列最大的hihi的和小于Limt的情況下每個序列gigi的和的最大值最小。

---

解題思路

我們二分最小的gigi的和的最大值
首先一個O(n2)O(n2)的dp想法，用fifi表示分割到第i個時最大的hihi的和的最小值。
動態轉移：

fi=min{f[j]+max{hj,hj+1,hj+2...hi?1,hi}}fi=min{f[j]+max{hj,hj+1,hj+2...hi?1,hi}}

我們考慮如何優化，每次有新的max只會在產生更大的hihi時，于是我們可以用一個nextinexti表示最近的hnext>hihnext>hi，然后我們可以二分快速找到滿足小于你目前二分到的答案的最小的位置。
時間復雜度O(n2+n??(log?n)2)O(n2+n(logn)2)
是不是感覺時間復雜度沒有變化，巧了！它就是A了

---

代碼

#include<cstdio> #include<algorithm> #include<cstring> #define H 20010 #define ll long long using namespace std; int n,h[H],g[H],z[H],next[H],num[H],tot; ll sum[H],L,f[H],ans,l,r; int find(int x,int need)//二分滿足條件的最小值 {int l=x,r=n;while(l<r){int mi=(l+r)/2;if(sum[mi]-sum[x-1]>=need) r=mi;else l=mi+1;}return l; } bool check(int x) {memset(f,127/3,sizeof(f));f[1]=0;for (int i=1;i<=n;i++)//dp{int k=find(i,x),y=i,add=h[y];if (sum[k]-sum[i-1]>x) k--;while(y<=k){f[y]=min(f[y],f[i]+add);add=h[y];y=next[y];}f[k+1]=min(f[k+1],f[i]+add);}return f[n+1]<=L; } int main() {scanf("%d%lld",&n,&L);for(int i=1;i<=n;i++){scanf("%d%d",&h[i],&g[i]);sum[i]=sum[i-1]+g[i];}num[1]=n+1;z[1]=2147483647;tot=1;for (int i=n;i;i--)//暴力next數組{while (z[tot]<=h[i]) tot--;next[i]=num[tot];++tot;num[tot]=i;z[tot]=h[i];} l=1;r=sum[n];ans=r;while(l<=r)//二分{int mid=(l+r)>>1;if (check(mid)) {if (mid<ans)ans=mid;r=mid-1;}else l=mid+1;}printf("%lld",ans); }

總結

以上是生活随笔為你收集整理的jzoj3463-军训【双重嵌套二分,随机数据水法】的全部內容，希望文章能夠幫你解決所遇到的問題。

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