3061.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Source

Problem Id:3061  User Id:fzk 
Memory:836K  Time:46MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <memory.h>
#include <algorithm>

__int64 a[100000], s;

int main( ) {
	int t, n, i, j, ans;
	scanf( "%d", &t );

	while( t-- ) {
		scanf( "%d%I64d", &n, &s );
		for( i=0; i<n; i++ )
			scanf( "%d", a+i );
		for( i=1; i<n; i++ )
			a[i] += a[i-1];

		ans = n+1;
		for( i=0, j=0; ; i++ ) {
			for( ; j<n&&a[j]-a[i]<s; j++ )
				;
			if( j >= n )
				break;
			if( j-i<ans )
				ans = j-i;
		}
		if( ans > n )
			ans = 0;
		printf( "%d\n", ans );
	}
	return 0;
}