【NOIP】排座椅

此题是一道十分考察细节的一道题。

此题就是让我们求的矩阵里，分割出条横线和条竖线，要求两两相邻的点，尽可能多的不再相邻。

题目已经告诉你了，这是一道贪心！！！

为什么是贪心呢？？？

要使答案最优，肯定要让条横线和条竖线要穿过尽可能多的会讲话的两个人！

如图：

如果只有一条横线和竖线上图中的最优解，很明显是这样：

所以我们的贪心是成立的

我们需要用结构体维护能穿过的讲话同桌个数和从第几行（列）分割的！
然后按照能穿过的同桌个数由大到小排序，最后输出答案。

code：

统计当前行列能穿过的同桌个数
if(x==x2){
    int yy=min(y,y2);
    cy[yy].x++;
    cy[yy].id=yy    从yy开始分割的
}
else if(y==y2){
    int xx=min(x,x2);    求最小可以防便后面输出处理
    cx[xx].x++;
    cx[xx].id=xx;   从xx开始分割的
    }

由大到小排序。
sort(cx+1,cx+1+m,cmp);
sort(cy+1,cy+1+n,cmp);

输出答案。

然后你照着码了一下代码会发现。。。 WA10分

WA10分，那我怎么可能服气，于是我手构了一组十分坑人的数据：

4 6 2 1 3
1 1 2 1
3 1 4 1
3 4 4 4

程序输出：

3 1
0

我手算了一下，发现答案没问题，我万思不得其解，然后看了看题目。。。。。

心中一万只羊驼在奔腾！！！

咳咳，回到正题

既然要保证 && 那么，我们就可以将 排序，即可AC！

code：

#include<bits/stdc++.h>
using namespace std;
int m,n,a,b,d;
struct node{int x,id;};
node cx[1005],cy[1005];
对能穿过同桌个数进行由大到小排序
bool cmp(node a,node b){return a.x>b.x;}
对所有最优解进行id的有小到大排序
bool cmp_id(node a,node b){return a.id<b.id;};
int main(){
    scanf("%d %d %d %d %d",&m,&n,&a,&b,&d);
       a表示a条横线，b表示b条竖线
    for(int i=1;i<=d;i++){
        int x,y,x2,y2;
        scanf("%d %d %d %d",&x,&y,&x2,&y2);
              统计当前行列能穿过的同桌个数
        if(x==x2){
            int yy=min(y,y2);
            cy[yy].x++;     统计个数
            cy[yy].id=yy;   标记所在列
        }
        else if(y==y2){
            int xx=min(x,x2);
            cx[xx].x++;
            cx[xx].id=xx;   标记所在行
        }
    }

        找出最优解
    sort(cx+1,cx+1+m,cmp);
    sort(cy+1,cy+1+n,cmp);
        对最优解排序
    sort(cx+1,cx+1+a,cmp_id);
    sort(cy+1,cy+1+b,cmp_id);
    for(int i=1;i<a;i++)
        printf("%d ",cx[i].id);
    printf("%d\n",cx[a].id);
    for(int i=1;i<b;i++)
        printf("%d ",cy[i].id);
    printf("%d\n",cy[b].id);
    return 0;完美结束
}