七夕祭

title: 七夕祭
date: 2024-01-03 22:47:05
tags:

传送门

题目大意

解题思路

行的感兴趣的摊点或者列的感兴趣的摊点的数量能被行数或者列数整除，则能够实现要求。“均分”思想，设总感兴趣摊点数 $T$ 和行数列数 $n$，当前感兴趣的摊点数超过 $\frac{T}{n}$ 则将多余的感兴趣摊点数 $a_i - \frac{T}{n} $转移给旁边的；如果小于 $\frac{T}{n}$，则旁边向其转移 $\frac{T}{n}$ - $a_i$ 个。我们向每一行或每一列减去 $\frac{T}{n}$ ，最后前缀和得到的结果为 0，这个结果是等价的，那么我们就将最小转换次数的问题转化成求每个点到该点的距离总和最短。参考 “货仓选址”，中位数的性质可以得出结果。

代码实现

#include<iostream>
#include<string.h>
#include<cstring>
#include<unordered_map>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<math.h>
#define bpt __builtin_popcountll

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;

const int N = 2E6 + 10, mod = 998244353;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

const int MOD = 998244353;

int row[N], col[N];
ll c[N];
int T;
ll get(int *a, int n)
{
	ll ans = T / n;
	for (int i = 1; i <= n; i++) {
		c[i] = a[i] - ans;
	}

	for (int i = 1; i <= n; i++) {
		c[i] += c[i - 1];
	}
	
	sort(c + 1, c + n + 1);
	int mid = c[n / 2 + 1];
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += abs(c[i] - mid);
	}
	return sum;
}
int main()
{
	int n, m;
	cin >> n >> m >> T;
	for (int i = 0; i < T; i++) {
		int l, r;
		cin >> l >> r;
		row[l] ++, col[r] ++;
	}
	if (T % m && T % n) {
		puts("impossible");
	}
	else if (T % n) {
		cout << "column" << ' ' << get(col, m);
	}
	else if (T % m) {
		cout << "row" << ' ' << get(row, n);
	}
	else {
		cout << "both" << ' ' << get(row, n) + get(col, m);
	}
}