一.题目链接：
七夕祭
二.题目大意：
中文题不解释.
三.分析：
{
根据移动规则易得：
上下交换两个点，该列中所需摊位个数不变.
左右交换两个点，该行中所需摊位个数不变.
那不妨先上下移动实现 row ，再左右移动 实现 col.
立即推：若 t 为 n 的倍数，则可实现 row；若 t 为 m 的倍数，则可实现 col.
下面只讨论如何实现 row，col 类比即可.
{
根据题目描述可得，这是要进行 行的部分交换，使得每行的元素个数均相等.
不过这是个环形，为了简化问题，我们先考察线型的问题.
{
即：有一行元素，每个相邻的元素进行部分交换，最终使得每个元素相同.
这个问题很简单，只需要 "多退少补" 到下一个元素即可.
例如：设每个元素的个数为 a[i]，平均数为 mean.
那么可由贪心解决
若 a[1] > mean，则第一个人将 a[1] - mean 个给第二个人.
若 a[1] < mean，则第一个人从第二个人那里取走 a[1] - mean 个.
即：使第一个人达到目标的最少交换次数为 |a[1] - mean|.
同理，对 [2, n] 进行相同操作.
由于第一步只是[1，2]之间的元素交换，所以 sum[2]（前缀和）不变.
所以第二步所需的交换次数为 |2 * mean - sum[2]|
到这里我们可以发现，总共的交换次数为
现在我们对这个式子变形
设
则交换次数为
我们可以注意到：s[n] == 0 是恒成立的（因为元素总数是不变的）.
}
现在我们再来讨论环形的情况.
根据线型，我们知道必定存在一个数 k，使得第 k 行不需要与第 k % n + 1 行进行元素交换.
把环断开，这样问题就转换为了线型问题.
即对于一个数 k：
序列 前缀和
A[k + 1] s[k + 1] - s[k]
A[k + 2] s[k + 2] - s[k]
............ .....................
A[n] s[n] - s[k]
A[1] s[1] + s[n] - s[k]
A[2] s[2] + s[n] - s[k]
............ .....................
A[k] s[k] + s[n] - s[k]
又因为 s[n] == 0
所以：
序列 前缀和
A[k + 1] s[k + 1] - s[k]
A[k + 2] s[k + 2] - s[k]
............ .....................
A[n] s[n] - s[k]
A[1] s[1] - s[k]
A[2] s[2] - s[k]
............ .....................
A[k] s[k] - s[k]
即：求一个数 k，使得 
}
我们把序列 s 排序，即求一个数 k，使得第 k 个位置的点与其他点的距离和最小.
假设第 k 个点左边有 p 个点，右边有 q 个点.
若 k 向右移动一个点，则左边的点距离都加 1，右边的点的距离都减 1，距离和减少了 q - p.
若 k 向左移动一个点，则左边的点距离都减 1，右边的点的距离都加 1，距离和减少了 p - q.
由此可得，k 应选取中位数.
}
四.代码实现：
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <bitset>
#include <vector>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define eps 1e-8
#define lc k * 2
#define rc k * 2 + 1
#define pi acos(-1.0)
#define ll long long int
using namespace std;
const int M = (int)1e5;
const ll mod = (ll)1e9 + 7;
const int inf = 0x3f3f3f3f;
struct node
{
int x, y;
} s[M + 5];
int row_cnt[M + 5];
int col_cnt[M + 5];
int row_sum[M + 5];
int col_sum[M + 5];
int main()
{
int n, m, t;
scanf("%d %d %d", &n, &m, &t);
memset(row_cnt, 0, sizeof(row_cnt));
memset(col_cnt, 0, sizeof(col_cnt));
for(int i = 1; i <= t; ++i)
{
scanf("%d %d", &s[i].x, &s[i].y);
row_cnt[s[i].x]++;
col_cnt[s[i].y]++;
}
bool row_flag = !(t % n);
bool col_flag = !(t % m);
if(!row_flag && !col_flag)
printf("impossible\n");
else
{
ll row_change = 0;
ll col_change = 0;
if(row_flag)
{
int mean = t / n;
for(int i = 1; i <= n; ++i)
{
row_cnt[i] -= mean;
row_sum[i] = row_sum[i - 1] + row_cnt[i];
}
sort(row_sum + 1, row_sum + n + 1);
int pos = n / 2 + 1;
for(int i = 1; i <= n; ++i)
row_change += (ll)abs(row_sum[i] - row_sum[pos]);
}
if(col_flag)
{
int mean = t / m;
for(int i = 1; i <= m; ++i)
{
col_cnt[i] -= mean;
col_sum[i] = col_sum[i - 1] + col_cnt[i];
}
sort(col_sum + 1, col_sum + m + 1);
int pos = m / 2 + 1;
for(int i = 1; i <= m; ++i)
col_change += (ll)abs(col_sum[i] - col_sum[pos]);
}
if(row_flag && !col_flag)
printf("row %lld\n", row_change);
else if(!row_flag && col_flag)
printf("column %lld\n", col_change);
else if(row_flag && col_flag)
printf("both %lld\n", row_change + col_change);
}
return 0;
}
京公网安备 11010502036488号