题意转化
给定行黑格数 和列黑格数 ，保证 ，构造一个 的 01 矩阵（# 为 1，. 为 0），使得第 行和为 ，第 列和为 。保证有解，输出任意解。
贪心构造法
这是一个经典的 Gale–Ryser 模型，可以用类似“列容量优先”的贪心构造：
- 将所有列视为容器，容量为 ，记录原始列号。
- 将列按容量降序排列。
- 依次处理每一行 ：
- 选择当前容量最大的前 列，在这些列对应的位置填
#。 - 这些列的容量减 1。
- 重新将列按容量降序排序（为下一行准备）。
- 选择当前容量最大的前 列，在这些列对应的位置填
- 所有行处理完毕后即得合法方案。
正确性：由于输入保证有解，贪心过程永远不会使列容量变为负数，最终恰好满足所有行列和。
复杂度
每行需要排序一次，复杂度 。对于 ，最坏运算量约 ，在 C++ 中完全可接受。也可用优先队列优化到 ，但对本题范围没有必要。
代码（C++14）
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int &x : a) cin >> x;
for (int &x : b) cin >> x;
vector<pair<int, int>> cols(m);
for (int j = 0; j < m; ++j) cols[j] = {b[j], j};
sort(cols.begin(), cols.end(), greater<>());
vector<string> ans(n, string(m, '.'));
for (int i = 0; i < n; ++i) {
int need = a[i];
for (int k = 0; k < need; ++k) {
int j = cols[k].second;
ans[i][j] = '#';
cols[k].first--;
}
sort(cols.begin(), cols.end(), greater<>());
}
for (auto &s : ans) cout << s << '\n';
return 0;
}
暂无评论