2566.txt

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

Problem Id:2566  User Id:fzk 
#include"stdio.h"
#include"algorithm"
#include"math.h"
using namespace std;
int sum[100010];
int *id[100010];
const bool cmp( int *a, int *b )
{
	return *a<*b;
}
int main()
{
	int n,m,i,t,j,a,b,ans,temp,k;
	while( 1 )
	{
		scanf( "%d %d", &n, &m );
		if( n == 0 && m == 0 ) break;		
		sum[0] = 0;
		id[0] = sum;
		for( i=1; i<=n; i++ )
		{
			scanf( "%d", &sum[i] );
			
			id[i] = sum + i;
			sum[i] += sum[i-1];
		}
		n++;
		sort( id, id+n, cmp );
		for( k=0; k<m; k++ )
		{
			scanf( "%d", &t );
			ans = 2000000000;
			for( i=0,j=1; i<n; i++ )
			{
				if( i >= j ) j++;
				if( j >= n ) break;
				while( j<n-1 && *id[j]-*id[i] < t )
					j++;
				if( ( temp = abs( *id[j] - *id[i] - t ) ) < ans )
					a = i, b = j, ans = temp;
				if( j-1 > i && ( temp = abs( *id[j-1] - *id[i] - t ) ) < ans )
					a = i, b = j-1, ans = temp;
			}
			if( id[a] > id[b] )swap( a, b );
			printf( "%d %d %d\n", abs( *id[a] - *id[b] ), id[a]-sum+1, id[b]-sum );
		}
	}
	return 0;			 

}