算法竞赛进阶指南-0x05-七夕祭
题目链接
这道题是我迄今为止做过最为复杂的思维题之一，我敢肯定我自己肯定无法独立想出此题的解法。
首先需要知道一点：如果只对行进行操作，不对列进行操作，那么每一列的二次元摊位（？）数量是不变的。因此可以先单独地对行进行操作，将每一行的二次元摊位数量操作成相等之后再对列操作，把将行操作成相等所需操作数与将列操作成相等所需操作数相加就能得到整个所需操作数了。
由于行跟列互不影响，如果二次元摊位总数t能被行数n整除，就表示可以将摊位均分到每个行中，对列也是如此。
然后如何求出将行/列处理成全部相等所需最小的操作数？
首先，假设给的不是环而是链。假设我们需要将这行数
的值全部变为2。
记sum[i]为“将长度为i的前缀中所有数全变为2后，该前缀向后“贡献”的值”。
什么意思？比如说，若想将长度为1的前缀，也就是第一个数1变为2，需要从第二个数拿1过来。由于整个序列的数的和是不变的，这个长度为1的前缀对整个序列的贡献就是-1，也就是sum[1] = -1。
之后，要再将长度为2的前缀中的所有数变为2。要单独将3这个数变成2需要3-2=1。所以将长度为2的前缀全部变成2后，对整个序列的贡献是sum[2] = sum[1] + 1 = 0。
由此可以得出
1
| sum[i] = sum[i - 1] + a[i] - tar;
|
其中a[i]表示序列的第i个值，tar表示需要变成的目标数。
将长度为i的前缀变成目标数所需的操作数，其实就是这个前缀的每个前缀的这个“贡献”的绝对值之和。因为值只能再相邻数之间传递，这个贡献实际上可以看作“当前数从后面的数接收到的数”。由于这个数可能是负数，所以需要取绝对值相加，长度为n的前缀（也就是整个序列）都变成目标数所需的操作数也就是
i=1∑n∣sum[i]∣
之后就是成环的事了。放在环中，相当于允许把原链的的一个前缀截断，接在原链的后面。假设将[1, k]截断接到了后面，操作数就变成了
i=k+1∑n(∣sum[i]−sum[k]∣)+i=1∑k(∣sum[i]+sum[n]−sum[k]∣)
只要事先保证了可以整除，sum[n] == 0总是成立的，所以上式可化为
i=k+1∑n(∣sum[i]∣−∣sum[k]∣)+i=1∑k(∣sum[i]−sum[k]∣)
即
i=1∑n∣sum[i]−sum[k]∣
在已知sum的情况，想使得这个式子最小，需要使sum[k]为sum的中位数。这可以类比成在一个数轴上找出离所有点距离之和最小的点离所有点的最小距离
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
long long sumx[100005], sumy[100005];
int main()
{
int n, m, i, j, x, y;
long long tar, t, res = 0, tp;
scanf("%d%d%lld", &n, &m, &t);
for (i = 1; i <= n; i++)
sumx[i] = 0;
for (i = 1; i <= m; i++)
sumy[i] = 0;
for (i = 1; i <= t; i++)
{
scanf("%d%d", &x, &y);
sumx[x]++;
sumy[y]++;
}
if (t % n == 0)
{
sumx[0] = 0;
tar = t / n;
for (i = 1; i <= n; i++)
sumx[i] = sumx[i - 1] + sumx[i] - tar;
sort(sumx + 1, sumx + 1 + n);
tp = sumx[(n + 1) >> 1];
for (i = 1; i <= n; i++)
{
if (sumx[i] > tp)
res += sumx[i] - tp;
else
res += tp - sumx[i];
}
}
if (t % m == 0)
{
sumy[0] = 0;
tar = t / m;
for (i = 1; i <= m; i++)
sumy[i] = sumy[i - 1] + sumy[i] - tar;
sort(sumy + 1, sumy + 1 + m);
tp = sumy[(m + 1) >> 1];
for (i = 1; i <= m; i++)
{
if (sumy[i] > tp)
res += sumy[i] - tp;
else
res += tp - sumy[i];
}
}
if (t % n && t % m)
{
printf("impossible");
return 0;
}
if (t % m)
{
printf("row %lld", res);
return 0;
}
if (t % n)
{
printf("column %lld", res);
return 0;
}
printf("both %lld", res);
return 0;
}
|