5801: 七夕祭（贪心）

　　　　　　　　　　　　　　　　　　5801: 七夕祭

时间限制(普通/Java):1000MS/3000MS 内存限制:65536KByte
总提交: 41 测试通过:16

描述

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。于是TYVJ今年举办了一次线下七夕祭。Vani同学今年成功邀请到了cl同学陪他来共度七夕，于是他们决定去TYVJ七夕祭游玩。

TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。

不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。

输入

第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。

接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。

输出

首先输出一个字符串。如果能满足Vani的全部两个要求，输出both；如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；如果只能使各列中cl感兴趣的摊点数一样多，输出column；如果均不能满足，输出impossible。

如果输出的字符串不是impossible，接下来输出最小交换次数，与字符串之间用一个空格隔开。

样例输入

2 3 4 1 3 2 1 2 2 2 3

样例输出

row 1

提示

样例输入2

3 3 3

1 3

2 2

2 3

样例输出2
both 2

解题思路：这个问题等于环形的纸牌均分问题把每一行每一列看成一个堆

 1 #include <iostream>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 int n,m,k;
 8 const int N=100005;
 9 typedef long long ll;
10 ll arr[N],brr[N];
11 ll dp[N],ff[N],sum;
12 
13 int read(){
14     int x=0,f=1;
15     char ch=getchar();
16     while(ch<'0'||ch>'9'){
17         if(ch=='-') f=-1;
18         ch=getchar();
19     }
20     while(ch>='0'&&ch<='9'){
21         x=(x<<1)+(x<<3)+(ch^48);
22         ch=getchar();
23     }
24     return x*f;
25 }
26 
27 int main(){
28     cin>>n>>m>>k;
29     for(int i=1,d1,d2;i<=k;i++){
30         d1=read();
31         d2=read();
32         arr[d1]++;
33         brr[d2]++;
34     }
35     if(k%n!=0&&k%m!=0) cout << "impossible" << endl;
36     else{
37         if(k%n==0){
38             int row=k/n;   //每行的个数
39             dp[1]=arr[1]-row;
40             for(int i=2;i<=n;i++){
41                 dp[i]=dp[i-1]+arr[i]-row;
42             }
43             sort(dp+1,dp+1+n);
44             ll mid=dp[(n+1)>>1];
45             for(int i=1;i<=n;i++){
46                 sum+=abs(dp[i]-mid);
47             }
48         }
49         if(k%m==0){
50             int col=k/m;
51             ff[1]=brr[1]-col;
52             for(int i=2;i<=m;i++){
53                 ff[i]=ff[i-1]+brr[i]-col;
54             }
55             sort(ff+1,ff+1+m);
56             ll mid=ff[(m+1)>>1];
57             for(int i=1;i<=m;i++){
58                 sum+=abs(ff[i]-mid);
59             }
60         }
61         if(k%n==0&&k%m==0) cout << "both " << sum << endl;
62         else if(k%n==0) cout << "row " << sum << endl;
63         else cout << "column " << sum << endl;
64     }
65     return 0;
66 }

View Code