Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

总是WA...有什么特殊注意的地方吗?

Posted by Fudapeng at 2005-08-16 12:12:00 on Problem 2566
#include "iostream.h"
#include "string.h"
#include "stdlib.h"
#include "fstream.h"
const long int maxn=110000;
long int h[maxn],f[maxn],n,len,b,e,ans;

int sort(long int b,long int e)
{
	long int i=b,j=e,mid=h[f[rand()%(e-b)+b]],k;
	while(i<=j)
	{
		while(h[f[i]]<mid) i++;
		while(h[f[j]]>mid) j--;
		if (i<=j)
		{
			k=f[i]; f[i]=f[j]; f[j]=k;
			i++; j--;
		}
	}
	if (b<j) sort(b,j);
	if (i<e) sort(i,e); 
	return 0;
}

long int find(long int cost)
{
	long int b=0,e=n;
	while(e-b>1)
		if (h[f[(b+e)/2]]>=cost) e=(b+e)/2; else b=(b+e)/2;
	while(b>0)
		if (h[f[b]]!=h[f[b-1]]) return b;
		else b--;
	return b;
}

int check(long int k,long int t,long int c)
{
	if (f[k]==t) return 0;
	long int cost=abs(h[f[k]]-c); 
	if (cost<ans)
	{
		ans=cost;
		if (f[k]<t) { b=f[k]+1; e=t; }
		else { b=t+1; e=f[k]; }
	}
	return 0;
}

int out()
{
	long int i;
	for (i=0;i<=n;i++)
		cout<<h[f[i]]<<' ';
	cout<<endl;
	return 0;
}

int main()
{
//    ifstream cin ("1.in");
//	ofstream cout ("1.out");
	while(true)
	{
		cin>>n>>len; if ((n==0)&&(len==0)) break;
		long int i,j;
		h[0]=0; 
		for (i=1;i<=n;i++)
		{ cin>>h[i]; h[i]+=h[i-1]; }
		for (i=0;i<=n;i++)
			f[i]=i;	

		sort(0,n); //out();

		for (i=1;i<=len;i++)
		{
			long int k,k1,cost,l;
			ans=214748000;
			cin>>k;
			for (j=0;j<=n;j++)
				for (l=0;l<2;l++)
				{
					if (l==0) cost=h[j]+k; else cost=h[j]-k;
					k1=find(cost); 

					check(k1,j,cost); k1++;
					while((h[f[k1]]==h[f[k1-1]])&&(k1<n)) { check(k1,j,cost); k1++; }
					do { check(k1,j,cost); k1++; } while((k1<=n)&&(h[f[k1]]==h[f[k1-1]]));
				}
			if (b==0) ans=abs(h[e]); else ans=abs(h[e]-h[b-1]);
			cout<<ans<<' '<<b<<' '<<e<<endl;
		}
	}
//	cout.close();
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator