橫向通道只會影響縱向相鄰的同學，且各個通道之間互不影響。每次設置通道選擇能夠隔開更多同學的，最終得到的值也會最大；縱向通道亦如此。
以下是我的代碼：
#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 閱讀(551)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：基礎/模擬