横向通道只会影响纵向相邻的同学，且各个通道之间互不影响。每次设置通道选择能够隔开更多同学的，最终得到的值也会最大；纵向通道亦如此。
以下是我的代码：
#include<iostream>
#define maxn 1007
using namespace std;
typedef struct
{
long num,cnt;
}type;
void Qsort(type *a,long l,long r)
{
long i=l,j=r,m=a[(l+r)/2].cnt;
do{
while(a[i].cnt>m) i++;
while(a[j].cnt<m) j--;
if(i<=j)
{
type t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(l<j) Qsort(a,l,j);
if(i<r) Qsort(a,i,r);
}
void Qsort2(long *a,long l,long r)
{
long i=l,j=r,m=a[(l+r)/2];
do{
while(a[i]<m) i++;
while(a[j]>m) j--;
if(i<=j)
{
long t=a[i];a[i]=a[j];a[j]=t;
i++;j--;
}
}while(i<=j);
if(l<j) Qsort2(a,l,j);
if(i<r) Qsort2(a,i,r);
}
long m,n,k,l,d;
type hang[maxn],lie[maxn];
long ans1[maxn],ans2[maxn];
int main()
{
cin>>m>>n>>k>>l>>d;
for(long i=1;i<=m;i++)
{
hang[i].num=i;hang[i].cnt=0;
}
for(long i=1;i<=n;i++)
{
lie[i].num=i;lie[i].cnt=0;
}
for(long i=1;i<=d;i++)
{
long x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
if(x1==x2)
lie[(y1<y2?y1:y2)].cnt++;
else
hang[(x1<x2?x1:x2)].cnt++;
}
Qsort(hang,1,m);
Qsort(lie,1,n);
for(long i=1;i<=k;i++)
ans1[i]=hang[i].num;
for(long i=1;i<=l;i++)
ans2[i]=lie[i].num;
Qsort2(ans1,1,k);
Qsort2(ans2,1,l);
for(long i=1;i<=k;i++)
{
if(i!=1) cout<<" ";
cout<<ans1[i];
}
cout<<endl;
for(long i=1;i<=l;i++)
{
if(i!=1) cout<<" ";
cout<<ans2[i];
}
cout<<endl;
return 0;
}
posted on 2010-10-30 00:10
lee1r 阅读(509)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：基础/模拟