比赛 |
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;
}