http://codeforces.com/problemset/problem/1250/G
题意： 给出两个数组a、b，你第i次增加ai分，对面增加bi分。你可以在每次加晚后重置，双方抵消分数（[3,7]变为[0,4]），当一个人的分数到达k分时失败。问最少的重置次数使得对方失败，你不失败。
解析： 想到枚举最后一次重置的位置，因为前面怎么重置都无所谓，而且后面在哪里到达k分可以知道。这个位置用尺取O(n)求出。
假设位置为x，那么相当于要求出x重置时的可行的最少次数。这个很明显，只要合法，越靠前，次数越少。同样是用尺取O(n)求出，所以总复杂度O(n)。
代码：
#include<bits/stdc++.h>using namespace std;#define LL long long#define debug(x) cerr<<#x<<":"<<x<<endlconst int maxn=2e5+9;LL a[maxn],b[maxn],sa[maxn],sb[maxn];#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)int dp[maxn],link[maxn];int n;LL k;inline LL val(int i,int pre,LL *s){ return s[i]-min(sa[pre],sb[pre]);}int main(){ int t;scanf("%d",&t); while(t--){ scanf("%d%lld",&n,&k); rep(i,1,n)scanf("%lld",&a[i]),sa[i]=a[i]+sa[i-1]; rep(i,1,n)scanf("%lld",&b[i]),sb[i]=b[i]+sb[i-1]; dp[0]=0; rep(i,1,n)dp[i]=1e9; int j=0; rep(i,1,n){ while(j<i&&(val(i,j,sa)>=k||val(i,j,sb)>=k))j++; if(j==i)break; link[i]=j; dp[i]=dp[j]+1; } int ans=1e9; int end; j=0; rep(i,0,n){ if(dp[i]==1e9)break; LL B=val(j,i,sb); while(j<n&&B<k){ j++; B+=b[j]; } if(j==n&&B<k)break; LL A=val(j,i,sa); if(A<k){ if(dp[i]<ans) ans=dp[i],end=i; } } if(ans==1e9)puts("-1"); else { printf("%dn",ans); while(ans--){ printf("%d ",end); end=link[end]; } puts(""); } }}