题解 | #[NOIP2008]排座椅#

这道题的策略是在当前未选择的行或列中选择能隔开同学最多的选项。

我们先用数组记录下每一行/列能够隔开的同学数量，然后对数组从大到小进行排序。但要注意，在排序过 程中，我们会损失行/列的编号信息，因此，需要事先将行/列编号记录下来。

#include<iostream>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
int m,n,k,l,d;
PII row[1000],col[1000];
bool cmp1(PII x,PII y)
{
    return x.first>y.first;
}
bool cmp2(PII x,PII y)
{
    return y.second>x.second;
}
int main()
{
    scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    for(int i=1;i<=m;i++) row[i].second=i;
    for(int i=1;i<=n;i++) col[i].second=i;
    for(int i=1;i<=d;i++)
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        if(x1==x2) col[min(y1,y2)].first++;
        if(y1==y2) row[min(x1,x2)].first++;
    }
    sort(row+1,row+m+1,cmp1);
    sort(col+1,col+m+1,cmp1);
    
    sort(row+1,row+1+k,cmp2);
    sort(col+1,col+1+l,cmp2);
    for(int i=1;i<=k;i++) printf("%d ",row[i].second);
    printf("\n");
    for(int i=1;i<=l;i++) printf("%d ",col[i].second);
    printf("\n");
}c