POJ 3061 Subsequence(尺取法)
Description
Input
Output
Sample Input
2 10 15 5 1 3 5 10 7 4 9 2 8 5 11 1 2 3 4 5
Sample Output
2 3
代码:
#include<cstdio> #define min(a,b) (a<b?a:b) using namespace std; int main() { int sum[100005]; int t,ans,i,N,S,temp,j; scanf("%d",&t)!=EOF; while(t--) { ans=1000005; sum[0]=0; scanf("%d%d",&N,&S); for(i=1;i<=N;i++) { scanf("%d",&temp); sum[i]=sum[i-1]+temp; } for(i=1,j=1;j<=N;j++) { if(sum[j]-sum[i]>=S) { while(sum[j]-sum[i]>=S&&i<=j) { ans=min(ans,j-i); i++; } } } if(ans==1000005)ans=0; printf("%d\n",ans); } return 0; }优质内容筛选与推荐>>