206004 - 排座椅

题目出处：NOIP 2008 普及组（其实挺水的）

题目大意：

同学们在教室中坐成了M行N列，有K条横向的通道，L条纵向的通道，D对同学上课时会交头接耳。用通道隔开交头接耳的同学。坐在第i行第j列的同学的位置是（i，j）。试改变同学们桌椅间通道的位置，编程给出最好的通道划分方案，使上课时交头接耳的学生对数最少。

题目分析

一道非常普通的贪心+排序题。

题目思路

因为是贪心+排序，贪心贪在把过道放在最多对讲话同学旁，拆散的越多，留下的越少。

各部分处理

1. 输入。

输入同时需要记录讲话的同学是一左一右还是一前一后。代码片断如下所示：

 int M,N,K,L,D,x1,x2,y1,y2;//x表示聊天同学的行，y表示列。
  scanf("%d %d %d %d %d",&M,&N,&K,&L,&D);
  for(int i=1; i<=D; i++)  //输入
  {
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    if (x1!=x2)          //x,y 指x行y列，若不相等就是一左一右。
	  b[min(x1,x2)]++;   //注意x1>x2的情况
    else a[min(y1,y2)]++;//否则就是一前一后。
  }

2.贪心

寻找阻隔聊天同学的最大值，每一次找出后取出到另一个数组，注意取出时应取出编号，否则需要定义结构体进行四次排序（行两次，列两次）。代码片断如下所示：

 int max=0,x=0;            //max统计最大的，x统计最大的数的下标。
  for(int i=1; i<=K; i++)  //找行，K是应找的个数
  {
    max=0，x=0;            //初始化
    for(int j=1; j<=M; j++)//遍历
      if (b[j]>max)        //判断
	    max=b[j],x=j;
    a1[i]=x;               //将下标存进答案数组中
    b[x]=-1;               //设置为-1，使在之后不会再次被提取
  }
  for(int i=1; i<=L; i++)  //找列
  {
    max=0;
    x=0;                   //初始化
    for(int j=1; j<=N; j++)//遍历
      if (a[j]>max)        //判断
	    max=a[j],x=j;
    b1[i]=x;               //将下标存进答案数组中
    a[x]=-1;               //设置为-1，使在之后不会再次被提取
  }

3.输出

对答案数组进行下标从小到大排序后输出。代码略。

期待的时刻——贴代码~

#include<bits/stdc++.h>
using namespace std;
#define maxn 1010
int lie[maxn],hang[maxn],ans1[maxn],ans2[maxn];//a行b列,a1,b1存答案
int main()
{
  int M,N,K,L,D,x1,x2,y1,y2;//x表示聊天同学的行，y表示列。
  scanf("%d %d %d %d %d",&M,&N,&K,&L,&D);
  for(int i=1; i<=D; i++)//输入
  {
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    if (x1!=x2)//（x,y)指x行y列，若不相等就是一左一右。
      hang[min(x1,x2)]++;//注意x1>x2的情况
    else lie[min(y1,y2)]++;//否则就是一前一后。
  }
  //贪心
  int Max=0,x=0;            //max计最大值，x统计最大值的下标。
  for(int i=1; i<=K; i++)  //找行，K是应找的个数
  {
    Max=0,x=0;                //初始化
    for(int j=1; j<=M; j++)   //遍历
      if (hang[j]>Max)        //判断
        Max=hang[j]，x=j；
    ans1[i]=x;                //将下标存进答案数组中
    hang[x]=-1;               //设置为-1，使在之后不会被提取
  }
  for(int i=1; i<=L; i++)    //找列
  {
    Max=0;
    x=0;                     //初始化
    for(int j=1; j<=N; j++)  //遍历
      if (lie[j]>Max)        //判断
        Max=lie[j],x=j;
    ans2[i]=x;               //将下标存进答案数组中
    lie[x]=-1;               //设置为-1，使在之后不会再次被提取
  }
  //输出
  sort(ans1,ans1+K+1)；
  sort(ans2,ans2+l+1)；
  for(int i=1; i<=K; i++)
    printf("%d ",ans1[i]);
  puts("");//换行
  for(int i=1; i<=L; i++)
    printf("%d ",ans2[i]);
  return 0;
}//珍爱生命，拒绝抄袭！

另附：老师的代码（本来我没看懂，后来发现原理是先把整个数组进行排序，在重新按开头顺序排序，数据大的时候排序耗时）

#include<bits/stdc++.h>
using namespace std;
struct node
{
  int count,id;
} x[1010],y[1010];
int m,n,k,l,d;
bool CMP1(node a,node b)
{
  return a.count>b.count;
}
bool CMP2(node a,node b)
{
  return a.id<b.id;
}
int main()
{
  scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
  for(int i=1,x1,y1,x2,y2; i<=d; i++)
  {
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    if(x1==x2)
    {
      y[min(y1,y2)].count++;
      y[min(y1,y2)].id=min(y1,y2);
    }
    else if(y1==y2)
    {
      x[min(x1,x2)].count++;
      x[min(x1,x2)].id=min(x1,x2);
    }
  }
  sort(x+1,x+1+m,CMP1);//这四次排序是先按照分开的同学数量从大往小排序
  sort(x+1,x+1+k,CMP2);//再按照该方向序号从小往大的顺序排，方便输出
  sort(y+1,y+1+n,CMP1);
  sort(y+1,y+1+l,CMP2);
  for(int i=1; i<=k; i++)
    printf("%d ",x[i].id);
  puts("");
  for(int i=1; i<=l; i++)
    printf("%d ",y[i].id);
  return 0;
}