题解
2026-11-08 18:33:28
发布于:新疆
11阅读
0回复
0点赞
下面是 A174978. 竖直落珠 的 C++ 代码。
一、思路
对每一列单独处理:统计该列中 1 的个数 c,则落珠后该列上面 n−c 行填 0,下面 c 行填 1。逐列操作即可,复杂度 O(n·m),n, m ≤ 100 完全够用。
二、C++ 代码
#include <bits/stdc++.h>
using namespace std;
/*
* A174978. 竖直落珠
*
* 题意:n 行 m 列盒子,每格为 0/1(1 表示有珠子)。
* 珠子只在原列向下落,最终每列珠子紧贴底部。
* 输出落珠后的表格。
*
* 做法:对每一列统计 1 的个数 c,
* 该列前 n-c 行为 0,后 c 行为 1。
*
* 数据范围:1 <= n, m <= 100,复杂度 O(n*m)。
*/
const int MAXN = 105;
int n, m;
int g[MAXN][MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> g[i][j];
// 逐列处理:先统计该列的珠子数,再重排
for (int j = 1; j <= m; ++j) {
int cnt = 0;
for (int i = 1; i <= n; ++i)
if (g[i][j] == 1) ++cnt;
// 上方 n-cnt 行为 0,下方 cnt 行为 1
for (int i = 1; i <= n; ++i)
g[i][j] = (i <= n - cnt) ? 0 : 1;
}
// 输出
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (j > 1) cout << ' ';
cout << g[i][j];
}
cout << '\n';
}
return 0;
}
三、要点说明
列内独立:珠子不能换列,所以每列互不影响,可以逐列求「该列最终的 0/1 分布」再写回。
填充位置:行号从上到下增大,所以第 1 行是顶部、第 n 行是底部;珠子沉底即第 n−cnt+1 到第 n 行为 1。
输出格式:相邻整数用一个空格隔开,行末不额外加空格,逐行换行。
复杂度:统计与重排各 O(n·m),总体 O(n·m),n, m ≤ 100 时瞬间完成。
样例验证
样例 #1:4 行 3 列,每列各有 2 颗珠子 → 前两行 0、后两行 1,与输出一致
样例 #2:3 行 4 列,第 2 列 2 颗、第 3 列 1 颗 → 输出第 2 行第 2 列为 1,第 2、3 行第 3 列为 1,与样例一致
这里空空如也







有帮助,赞一个