按 lunatic 说的方法做,不知哪里理解错了,一直TLE,一开始的上下界用了部分和最大最小

#include "stdio.h"
#include "stdlib.h"
#include<algorithm>
using namespace std;

const int M = 20001;

int a[M];
int n, k;
__int64 suml[M], sumr[M];
int topl, topr;

inline bool scmp(__int64 a,__int64 b)
{	return a<b;		}

int count( __int64 x, int l, int r )
{
	if( l + 1 == r ) return a[l]<= x;
	int ret = 0;
	int mid = (l+r)>>1;
	ret += count( x, l, mid );
	ret += count( x, mid, r );
	int i,j;
	suml[0] = 0;
	for( j = 1, i = mid-1; i >= l; i --, j ++)
		suml[j] = suml[j-1] + a[i];
	topl = j;
	sumr[0] = 0;
	for( j = 1, i = mid; i < r; i ++, j ++ )
		sumr[j] = sumr[j-1] + a[i];
	topr = j;
	sort(suml+1,suml+topl,scmp);
	sort(sumr+1,sumr+topr,scmp);
	i = 1; j = topr-1;
	while( j && i != topl )
	{
		if( suml[i] + sumr[j] <= x )
			ret += j, i ++;
		else
			j --;
	}
	return ret;
}

int main()
{
	int c = 1;
	while( scanf( "%d%d", &n, &k ) != EOF )
	{
		int i;
		__int64 sum , isum,s1=0,s2=0;
		sum = isum = 0;
		for( i = 0; i < n; i ++ )
			scanf( "%d", &a[i] );
		for(i=0;i<n;i++)
		{
			s1+=a[i];
			s2+=a[i];
			if(s1<0)s1=0;
			if(s2>0)s2=0;
			if(s1>sum)sum=s1;
			if(s2<isum)isum=s2;
		}
		__int64 mid, l = isum, r = sum;
		while( l + 1 < r )
		{
			mid = (l + r)/2;
			if( count(mid,0,n) >= k )
				r = mid;
			else
				l = mid;
		}
		if( count(l,0,n) >= k )
			r = l;
		printf( "Case %d: %I64d\n", c++, r );
	}
	return 0;
}

• 最前一段注释没用,不好意思! (0) 044100324 2007-10-05 20:03:21
• 删了下贴子，子贴都没了，我晕～～～ (1625) 044100324 2007-10-05 23:26:13