P1056 排座椅

admin

题目描述
上课的时候总会有一些同学和前后左右的人交头接耳，这是令小学班主任十分头疼的一件事情。不过，班主任小雪发现了一些有趣的现象，当同学们的座次确定下来之后，只有有限的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……bL，表示第b1列和b1+1列之间、第b2列和b2+1列之间、…、第bL列和第bL+1列之间要开辟通道，其中bi< bi+1，每两个整数之间用空格隔开（列尾没有空格）。

输入输出样例
输入样例#1：
4 5 1 2 3
4 2 4 3
2 3 3 3
2 5 2 4
输出样例#1：
2
2 4
说明


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

2008年普及组第二题

张笑宇

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int x,y,ix,iy,n;
   
5. const int mx=1100;
   
6. int sumx[mx],sumy[mx],i,j;
   
7. int nx[mx],ny[mx];///nx,ny相当于结构体
   
8. int main()
   
9. {
   
10.     cin>>x>>y>>ix>>iy>>n;
    
11.     for (i=1; i<=n; i++)
    
12.     {
    
13.         int r1,r2,c1,c2,r,c;
    
14.         cin>>r1>>c1>>r2>>c2;
    
15.         r=min(r1,r2),c=min(c1,c2);
    
16.         if (r1==r2) sumy[c]++;
    
17.         if (c1==c2) sumx[r]++;
    
18.     }
    
19.     /*
    
20.         for (i=x;i>=1;i--) cout<<sumx[i]<<" ";
    
21.         cout<<endl;
    
22.         for (j=1;j<=y;j++) cout<<sumy[j]<<" ";
    
23.         cout<<endl;
    
24.     */
    
25.     for (i=1; i<=x; i++) nx[i]=i;
    
26.     for (i=1; i<=y; i++) ny[i]=i;
    
27.     for (i=1; i<=x-2; i++)
    
28.         for (j=i+1; j<=x-1; j++)
    
29.         {
    
30.             if (sumx[i]<sumx[j])
    
31.             {
    
32.                 swap(sumx[i],sumx[j]);
    
33.                 swap(nx[i],nx[j]);
    
34.             }
    
35.         }
    
36.     sort(nx+1,nx+ix+1);
    
37.     for (i=1; i<=ix-1; i++) cout<<nx[i]<<" ";cout<<nx[ix]<<endl;
    
38. 
    
39.     for (i=1; i<=y-2; i++)
    
40.         for (j=i+1; j<=y-1; j++)
    
41.         {
    
42.             if (sumy[i]<sumy[j])
    
43.             {
    
44.                 swap(sumy[i],sumy[j]);
    
45.                 swap(ny[i],ny[j]);
    
46.             }
    
47.         }
    
48.     sort(ny+1,ny+iy+1);
    
49.     for (i=1; i<=iy-1; i++) cout<<ny[i]<<" ";cout<<ny[iy];
    
50.     return 0;
    
51. }
    

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int M,N,K,L,D,m,n,k,l,o;
   
5. int i,j,b1,b2;
   
6. struct row
   
7. {
   
8.     int x,r;
   
9. } s[1001];
   
10. struct cross
    
11. {
    
12.     int y,p;
    
13. }q[1001];
    
14. bool cmp1(row t,row h)
    
15. {
    
16.     return t.x>h.x;
    
17. }
    
18. bool cmp2(cross t,cross h)
    
19. {
    
20.     return t.y>h.y;
    
21. }
    
22. bool cmp3(row t,row h)
    
23. {
    
24.     return t.r<h.r;
    
25. }
    
26. bool cmp4(cross t,cross h)
    
27. {
    
28.     return t.p<h.p;
    
29. }
    
30. int main()
    
31. {
    
32.     cin>>M>>N>>K>>L>>D;
    
33.     for(i=1; i<=D; i++)
    
34.     {
    
35.         cin>>m>>n>>k>>l;
    
36.                                                                                                          ///for(o=1;o<=M;o++)
    
37.                                                                                                         ///   {
    
38.                                                                                                         ///     for(j=1;j<=N;j++)
    
39.                                                                                                           ///         cout<<a[i][j]<<" ";检查看过程用
    
40.                                                                                                            ///      cout<<endl;
    
41.                                                                                                            ///   }
    
42.         if(m==k)
    
43.          {
    
44.             q[min(n,l)].p=min(n,l);
    
45.             q[min(n,l)].y++;
    
46.          }
    
47.         if(n==l)
    
48.         {
    
49.             s[min(m,k)].r=min(m,k);
    
50.             s[min(m,k)].x++;
    
51.         }
    
52.     }
    
53.                                                                              ///for(o=1;o<=N;o++)cout<<y[o]<<" ";
    
54.                                                                               ///    cout<<endl;for(o=1;o<=M;o++)cout<<x[o]<<" ";同上
    
55.     sort(s+1,s+M,cmp1);
    
56.     sort(q+1,q+N,cmp2);
    
57.     b1=s[K].x;
    
58.     b2=q[L].y;
    
59.     sort(s+1,s+M,cmp3);
    
60.     sort(q+1,q+N,cmp4);
    
61.     for(i=1;i<=M; i++)
    
62.         if(s[i].x>=b1)cout<<s[i].r<<" ";
    
63.     cout<<endl;
    
64.     for(i=1;i<=N; i++)
    
65.         if(q[i].y>=b2)cout<<q[i].p<<" ";
    
66.     return 0;
    
67. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int m,n,k,l,d;
   
5. struct seat{
   
6.     int num;
   
7.     int s;
   
8. } x[1001],y[1001];
   
9. int x1,y1,x2,y2;
   
10. bool cmp(seat &a,seat &b)
    
11. {
    
12.     return a.s>b.s;
    
13. }
    
14. bool mmp(seat &a,seat &b)
    
15. {
    
16.     return a.num<b.num;
    
17. }
    
18. int main()
    
19. {
    
20.     cin>>m>>n>>k>>l>>d;
    
21.     for(int i=1;i<=m;i++)x[i].num=i;
    
22.     for(int i=1;i<=n;i++)y[i].num=i;
    
23.     for(int i=1;i<=d;i++)
    
24.     {
    
25.         cin>>x1>>y1>>x2>>y2;
    
26.         if(x1==x2)y[min(y1,y2)].s++;
    
27.         else x[min(x1,x2)].s++;
    
28.     }
    
29.     sort(x+1,x+m+1,cmp);
    
30.     sort(y+1,y+n+1,cmp);
    
31.     sort(x+1,x+k+1,mmp);
    
32.     sort(y+1,y+l+1,mmp);
    
33.     for(int i=1;i<=k;i++)cout<<x[i].num<<' ';cout<<endl;
    
34.     for(int i=1;i<=l;i++)cout<<y[i].num<<' ';
    
35.     return 0;
    
36. }
    

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. using namespace std;
    
12. int m,n,k,l,d,x11,y11,x22,y22;
    
13. struct hehe
    
14. {
    
15.         int bian,ji;
    
16. }a[5000],b[5000];
    
17. bool cmp(hehe x,hehe y)
    
18. {
    
19.         return x.ji>y.ji;
    
20. }
    
21. bool cmp1(hehe x,hehe y)
    
22. {
    
23.         return x.bian<y.bian;
    
24. }
    
25. int main()
    
26. {
    
27.         scanf("%d%d%d%d%d",&m,&n,&k,&l,&d);
    
28.         for(int i=1;i<=n;i++)
    
29.                 b[i].bian=i;
    
30.         for(int i=1;i<=m;i++)
    
31.                 a[i].bian=i;
    
32.         for(int i=1;i<=d;i++)
    
33.         {
    
34.                 scanf("%d%d%d%d",&x11,&y11,&x22,&y22);
    
35.                 if(x11==x22)
    
36.                         b[min(y11,y22)].ji++;
    
37.                 else if(y22==y11)
    
38.                         a[min(x11,x22)].ji++;
    
39.         }
    
40.         sort(a+1,a+m,cmp);sort(b+1,b+n,cmp);
    
41.         sort(a+1,a+k+1,cmp1);sort(b+1,b+l+1,cmp1);
    
42.         for(int i=1;i<=k;i++)
    
43.                 printf("%d ",a[i].bian);
    
44.         printf("\n");
    
45.         for(int i=1;i<=l;i++)
    
46.                 printf("%d ",b[i].bian);
    
47.         return 0;
    
48. }

复制代码