比赛 10101115 评测结果 AWWWWWWWWW
题目名称 矩形分割 最终得分 10
用户昵称 wangwangdog 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-11-15 11:15:57
显示代码纯文本
#include<stdio.h>
long n,m,shu[2001],heng[2001],shui[2001],hengi[2001],min,mm,nn,i,allheng,allshu,allhengi,allshui;
void qsort1 (long a,long b)
{
	long t1=a,t2=b,t3=heng[(a+b)/2];
	do
	{
		while(heng[t1]<t3)t1++;
		while(heng[t2]>t3)t2--;
		if(t1<=t2)
		{
			long o=heng[t1];
			heng[t1]=heng[t2];
			heng[t2]=o;
			t1++;
			t2--;
		}
	}
	while(t1<t2);
	if(t1<b)qsort1(t1,b);
	if(t2>a)qsort1(a,t2);
}
void qsort2 (long a,long b)
{
	long t1=a,t2=b,t3=shu[(a+b)/2];
	do
	{
		while(shu[t1]<t3)t1++;
		while(shu[t2]>t3)t2--;
		if(t1<=t2)
		{
			long o=shu[t1];
			shu[t1]=shu[t2];
			shu[t2]=o;
			t1++;
			t2--;
		}
	}
	while(t1<t2);
	if(t1<b)qsort1(t1,b);
	if(t2>a)qsort1(a,t2);
}
FILE *fin,*fout;
int main()
{
	fin=fopen("cut.in","rb");
	fout=fopen("cut.out","wb");
	fscanf(fin,"%ld%ld\n",&n,&m);
	allheng=0;
	allshu=0;
	for(i=1;i<=n-1;i++)
	{
		fscanf(fin,"%ld",&heng[i]);
		allheng=allheng+heng[i];
	}
	fscanf(fin,"\n");
	for(i=1;i<=m-1;i++)
	{
		fscanf(fin,"%ld",&shu[i]);
		allshu=allshu+shu[i];
	}
	qsort1(1,n-1);
	qsort2(1,m-1);
	nn=n-1;
	mm=m-1;
	allhengi=allheng;
	allshui=allshu;
	for(i=1;i<=n;i++)
		hengi[i]=heng[i];
	for(i=1;i<=m;i++)
		shui[i]=shu[i];
	while(nn>0||mm>0)
	{
		long pp=n-1;
		while(heng[pp]==-1)pp--;
		long qq=m-1;
		while(shu[qq]==-1)qq--;
		if(heng[pp]>=shu[qq]||mm==0)
		{
			min=min+heng[pp];
			heng[pp]=-1;
			nn--;
			
			for(i=1;i<=m;i++)
				if(shu[i]!=-1)shu[i]=shu[i]+shui[i];
		}
		if(heng[pp]<shu[qq]||nn==0)
		{
			min=min+shu[qq];
			shu[qq]=-1;
			mm--;
			for(i=1;i<=n;i++)
				if(heng[i]!=-1)heng[i]=heng[i]+hengi[i];
		}
	}
	fprintf(fout,"%ld",min);
	fclose(fin);
	fclose(fout);
	return 0;
}