题解：P10453 七夕祭

BLuemoon_ · 2024-11-28 14:20:20 · 题解

link

题意

给定一个 N\times M 的矩阵，其中有一些点是关键点，一次操作可以交换相邻两个点的关键性。问使每行每列关键点数量一致的最小移动步数。

前置知识

P2512 [HAOI2008] 糖果传递

即环形均分纸牌。

令 v 为 \{a_n\} 的平均值，a_i^{\prime}=a_i-v，\{s_n\} 为 \{a_i^{\prime}\} 的前缀和。

假设在第 k+1 个点断环成链，则前缀和变为：

可以发现全部减去了 s_k。那么答案就转化成了 \displaystyle\sum_{i=1}^{n}|s_i-s_k|。

就转化成了货仓选址问题，直接取中位数即可。

思路

由于交换行之间的点不会改变列的关键点数，交换列之间的点不会改变行的关键点数，我们可以把行列分开处理。

对于行，可以把每一行的关键点数当作糖果传递处理；对于列同理。

代码

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e5 + 5;

LL n, m, t, sl, sr, a[kMaxN], b[kMaxN], l[kMaxN], r[kMaxN], ls[kMaxN], rs[kMaxN], ans;
bool L, R;

int main() {
  cin >> n >> m >> t, L = t % n == 0, R = t % m == 0;
  for (int i = 1; i <= t; i++) {
    cin >> a[i] >> b[i], l[a[i]]++, r[b[i]]++;
  }
  if (!L && !R) {
    return cout << "impossible\n", 0;
  }
  cout << (L && R ? "both" : (L ? "row" : "column")) << ' ';
  sl = t / n, sr = t / m;
  if (L) {
    for (int i = 1; i <= n; i++) {
      l[i] -= sl, ls[i] = ls[i - 1] + l[i];
    }
  }
  if (R) {
    for (int i = 1; i <= m; i++) {
      r[i] -= sr, rs[i] = rs[i - 1] + r[i];
    }
  }
  sort(ls + 1, ls + n + 1), sort(rs + 1, rs + m + 1);
  if (L) {
    for (int i = 1; i <= n; i++) {
      ans += abs(ls[i] - ls[(n + 1) >> 1]);
    }
  }
  if (R) {
    for (int i = 1; i <= m; i++) {
      ans += abs(rs[i] - rs[(m + 1) >> 1]);
    }
  }
  cout << ans << '\n';
  return 0;
}