| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
干嘛都在YY2分法,很短的代码,O(n^2),79ms#include<stdio.h>
int sum[100001];
int main()
{
int t,n,s,i,d,b,min,j;
scanf("%d",&t);
while(t--)
{
b=0;
scanf("%d%d",&n,&s);
min=n+1;
for(i=1;i<=n;i++)
{
scanf("%d",&d);
sum[i]=sum[i-1]+d;
if(sum[i]-sum[b]>=s)
{
if(i-min>b) b=i-min;
for(j=b+1;j<i;j++)
{
if(sum[i]-sum[j]<s) break;
}
min=i-j+1;
b=i-min+1;
}
}
if(min>n) printf("0\n");
else printf("%d\n",min);
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator