Codeforces 1774D. Polynomial Round 2022 (Div. 1 + Div. 2, Rated, Prizes!) D(思维)
原题链接
简单
作者:
小小_88
,
2023-01-08 22:07:37
,
所有人可见
,
阅读 232
Same Count One
C++ 代码
/*
要想让每一列的 1 的数量相同,首先 1 的总数必须是行数的倍数,否则一定无解。
然后考虑如何操作,只需要实时记录每一行中 1 的数量。然后计算一下每一行应该有多少个 1.
然后将 1 过多的行上的 1 交换到 1 过少的行上即可,由于 1 只能在同一列进行交换,因此
可以枚举每一列,对于每一列可以交换的 1 和可以接收的空位进行交换,然后将方案存储即可
*/
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
void work()
{
int n, m;
scanf("%d%d", &n, &m);
vector<vector<int>> a(n + 1, vector<int>(m + 1));
vector<int> s(n + 1);
int cnt = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
scanf("%d", &a[i][j]);
s[i] += a[i][j];
cnt += a[i][j];
}
if(cnt % n)
{
puts("-1");
return;
}
int k = cnt / n;
vector<int> r1, r2;
vector<vector<int>> res;
for(int j = 1; j <= m; j++)
{
for(int i = 1; i <= n; i++)
{
if(s[i] > k && a[i][j]) r1.push_back(i);
if(s[i] < k && !a[i][j]) r2.push_back(i);
}
for(int i = 0; i < min(r1.size(), r2.size()); i++)
{
s[r1[i]]--, s[r2[i]]++;
res.push_back({r1[i], r2[i], j});
}
r1.clear(), r2.clear();
}
printf("%d\n", res.size());
for(int i = 0; i < res.size(); i++) printf("%d %d %d\n", res[i][0], res[i][1], res[i][2]);
}
int main()
{
int T;
scanf("%d", &T);
while(T--) work();
return 0;
}