pku2751.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 94 行

#include <stdio.h>
#include <stdlib.h>
typedef struct
{
	int time;
	int owner;
	int second;	
} Job;

int cp(const void *a, const void *b)
{
	Job *c = (Job *)a;
	Job *d = (Job *)b;
	return c->time - d->time;
}


int main()
{
	Job job[20002];
	int p[10001][2];
	int use[10001], order[10001];
	int i,j,n,fir,sec;
	int first[10001],second[10001];
	while(scanf("%d",&n)!=-1 && n>0)
	{
		for(i=0;i<n;i++)
		{
			scanf("%d",&fir);
			scanf("%d",&sec);
			
			p[i][0]=fir;
			p[i][1]=sec;
			
			job[2*i].time=fir;
			job[2*i].owner=i;
			job[2*i].second=0;
				
			job[2*i+1].time=sec;
			job[2*i+1].owner=i;
			job[2*i+1].second=1;
		}

		qsort(job,2*n,sizeof(job[0]),cp);

		for(i=0;i<n;i++)
		{
			use[i]=0;	
		}
		
		fir=0;
		sec=n-1;
		
		for(i=0;i<2*n;i++)
		{
			if(use[job[i].owner]) continue;
			if(job[i].second==0)
			{
				order[fir++]=job[i].owner;
			}
			else
			{
				order[sec--]=job[i].owner;	
			}	
			use[job[i].owner]=1;	
		}
		
		for(i=1,first[0]=p[order[0]][0];i<n;i++)
		{
			first[i]=first[i-1]+p[order[i]][0];
		}

		second[0]=first[0]+p[order[0]][1];
		
		for(i=1;i<n;i++)
		{
			if(second[i-1]<first[i])
			{
				second[i]=first[i]+p[order[i]][1];	
			}
			else
			{
				second[i]=second[i-1]+p[order[i]][1];	
			}	
		}
		
		printf("%d\n",second[n-1]);
	}
	
	return 0;
}