[acmm week12]二分+dp+单调队列

1004 抄作业

	Time Limit: 1sec    Memory Limit:256MB Description Zfree虽然平时很爱学习，但是他迫于生活所迫（比如设计cpu实验啊），这周数分作业只能抄答案了。 可是这是他第一次抄作业题目又多，于是他有些不想抄，因为他想玩会游戏再抄，于是他打算用一定的时间去抄作业（当然也可以不用完）。 而这可能抄不完，所以他会选择跳过几题不抄，为了尽量不被老师发现，他想知道他抄写的两题的题号最大间隔最小是多少？（间隔包括他第一个抄的题目前面的题目数量 和 最后一个题目后面的题目数量） Input 第一行 T，n 表示可以用来抄题目的总时间和题目数量(T,n<10^5) 第二行 n个数字，第i个数字表示抄写第i题要用的时间数(a[i]<T) Output 一个数字k，表示最多隔k题抄一题可以用T时间抄完题目 Sample Input  10 5 5 3 6 1 3 Sample Output 1

题意：n个数，选取若干个数，其中两个数之间的间隔最大为k，问k最小是多少。

题解：

要最大值最小，二分k，然后dp判断当前的k是否可行。
设dp[i]表示最大间隔不超过k的前提下，前i道题目中，选了第i道题，所用的最短时间。
dp[i]=min(dp[j])+time[i]， i-k-1<=j < i
这个方程最坏情况是n^2的，但这种形式的方程我们可以用一个单调队列来优化。对于当前的i，队列q储存的可能的j值，满足其dp值递增，每次先判断对首的元素是否>=i-k-1,不满足则出队；用队首元素更新dp[i]；若队尾的元素的dp值大于dp[i]则出队（这些元素此后都一定没有i优，不可能用于更新其他dp值），再把i放到队尾。这样总的复杂度就是O(nlogn)的。

 #include<bits/stdc++.h>
 using namespace std;

 const int N=;
 int a[N],f[N],g[N];
 int t,n;

 void init()
 {
     scanf("%d%d",&t,&n);
     for(int i=;i<=n;i++) scanf("%d",&a[i]);
     a[n+]=;
 }

 bool check(int k)
 {
     //f[i]=min(f[j])+a[i];  (i-k-1 <= j <= i-1)
     int l=,r=;
     f[]=;g[]=;
     for(int i=;i<=n+;i++)
     {
         while(l<=r && g[l]<i-k-) l++;
         f[i]=f[g[l]]+a[i];
         while(l<=r && f[g[r]]>f[i]) r--;
         g[++r]=i;
     }
     return f[n+]<=t;
 }

 void solve()
 {
     int l=,r=n,mid;
     while(l<r)
     {
         mid=(l+r)/;
         if(check(mid)) r=mid;
         else l=mid+;
     }
     printf("%d\n",l);
 }

 int main()
 {
     //freopen("a.in","r",stdin);
     init();
     solve();
     return ;
 }