NOIP 2008 排座椅(贪心)

小鱼儿 2022-05-16 02:51 109阅读 0赞

题目描述

上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的D对同学上课时会交头接耳。同学们在教室中坐成了M行N列，坐在第i行第j列的同学的位置是（i, j），为了方便同学们进出，在教室中设置了K条横向的通道，L条纵向的通道。于是，聪明的小雪想到了一个办法，或许可以减少上课时学生交头接耳的问题：她打算重新摆放桌椅，改变同学们桌椅间通道的位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。  
请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上课时交头接耳的学生对数最少。

输入

每组输入数据的第一行，有5个用空格隔开的整数，分别是M，N，K，L，D（2<=N, M<=1000，0<=K<M，0<=L<N，D<=2000）。  
接下来D行，每行有4个用空格隔开的整数，第i行的4个整数Xi，Yi，Pi，Qi，表示坐在位置(Xi, Yi)与(Pi, Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。  
输入数据保证最优方案的唯一性。

输出

每组输出共两行。  
第一行包含K个整数，a1 a2...aK，表示第a1行和a1+1行之间、第a2行和第a2+1行之间、...、第aK行和第aK+1行之间要开辟通道，其中ai<ai+1，每两个整数之间用空格隔开（行尾没有空格）。  
第二行包含L个整数，b1 b2...bk，表示第b1列和b1+1列之间、第b2列和第b2+1列之间、...、第bL列和第bL+1列之间要开辟通道，其中bi<bi+1，每两个整数之间用空格隔开（行尾没有空格）。  
  
  
下面是对样例数据的解释：

![pimg1077_1.jpg][]

上图中用符号\*、※、+标出了3对会交头接耳的学生的位置，图中3条粗线的位置表示通道，图示的通道划分方案是唯一的最佳方案。

分析：要想让交头接耳的学生对数最少，那么通道就要尽可能的隔开更多的学生，而输入数据又是保证他们前后相邻或者左右相邻的，因此，用两个数组，一个记录行，一个记录列，来记录各行各列的人数，然后从大到小依次找出K个行通道，也就是找K个行上人数多的，再以同样的方式找出L个列通道，也就是找L个列上人数多的，对于每次找的行通道和列通道，需要用两个数组来标记哪些行列位置被设置了通道，然后输出被标记的通道即可，具体细节看代码注释。

#include<map>
    #include<set>
    #include<cmath>
    #include<queue>
    #include<stack>
    #include<cstdio>
    #include<vector>
    #include<cctype>
    #include<cstring>
    #include<utility>
    #include<cstdlib>
    #include<iomanip>
    #include<iostream>
    #include<algorithm>
    #define Clear(x) memset(x,0,sizeof(x))
    #define fup(i,a,b) for(int i=a;i<b;i++)
    #define rfup(i,a,b) for(int i=a;i<=b;i++)
    #define fdn(i,a,b) for(int i=a;i>b;i--)
    #define rfdn(i,a,b) for(int i=a;i>=b;i--)
    typedef long long ll;
    typedef unsigned long long ull;
    using namespace std;
    const int maxn=1e3+7;
    int M,N,K,L,D;
    int h[maxn],l[maxn];//行，列
    int ph[maxn],pl[maxn];//需要打印(print)的行，列
    
    int read()
    {
        char ch=getchar();int ret=0,f=1;
        while(ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
        while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
        return f*ret;
    }
    
    void input()
    {
        Clear(h),Clear(l),Clear(ph),Clear(pl);
        M=read(),N=read(),K=read(),L=read(),D=read();
        int x1,y1,x2,y2;
        fup(i,0,D)
        {
            x1=read(),y1=read(),x2=read(),y2=read();
            if(x1==x2) l[min(y1,y2)]++;//因为a1通道表示的是a1列和a1+1列之间有通道，题上没有保证第二个一定比第一个的大,所以取较小的一个
            else h[min(x1,x2)]++;//和上面同理
        }
    }
    
    void print()
    {
        int flag=1;
        fup(i,0,M)
        {
            if(ph[i])
            {
                if(flag) flag=0;
                else printf(" ");
                printf("%d",i);
            }
        }
        printf("\n");
        flag=1;
        fup(i,0,N)
        {
            if(pl[i])
            {
                if(flag) flag=0;
                else printf(" ");
                printf("%d",i);
            }
        }
        printf("\n");
    }
    
    void slove()
    {
        fup(i,0,K)//设置行的通道
        {
            int max_pos=-1;//人数最多的一行的行标
            int max_value=-1;//人数最多的这一行的人数
            fup(j,1,M)
            {
                if(h[j]>max_value)
                {
                    max_value=h[j];
                    max_pos=j;
                }
            }
            ph[max_pos]=1;//标记这一行设置了通道
            h[max_pos]=0;//这一行已经设置为通道
        }
        fup(i,0,L)//设置列的通道
        {
            int max_pos=-1;
            int max_value=-1;
            fup(j,1,N)
            {
                if(l[j]>max_value)
                {
                    max_value=l[j];
                    max_pos=j;
                }
            }
            pl[max_pos]=1;//标记这一列设置了通道
            l[max_pos]=0;//这一列已被设置为通道
        }
        print();
    }
    
    int main()
    {
        input();
        slove();
        return 0;
    }

[pimg1077_1.jpg]: /images/20220516/562ef635607347b2b6440088c401689f.png