U654615 比特聚集（bit）补题报告
先看题目：
题目分析
我们有一个长度为的二进制字符串
，包含字符
'0'和'1'，至少有一个'1'。
可以交换相邻字符，每次交换算一次操作。
目标：让所有'1'连续排列（形成一段连续的'1'）。
求最少操作次数
思路分析
关键观察
最终
'1'聚集到连续的一段，但我们可以自由选择这个连续段的位置。我们只关心
'1'的相对位置变化，不关心'0'的具体分布（除了它们会占用位置）。交换相邻字符，相当于把一个
'1'向左或向右移动一位。把所有的
'1'聚集到一起，等价于把每个'1'移动到某个中心位置附近。这其实是一个经典问题：最小化所有
'1'移动到连续位置的总交换次数。
转化为数学模型
假设最终'1'的连续段是从位置 k 到位置 k+m−1，其中 m 是'1'的个数。
设原字符串中'1'的位置（下标从 1 开始）是：
p1,p2,…,pm
最终连续段的位置是：
k,k+1,…,k+m−1
那么把第 j 个'1'从 pj 移动到 k+j−1 需要的交换次数就是：
总操作次数为：
我们要选择一个整数 k 使得这个和最小。
化简
令 qj=pj−(j−1)，那么上式变成：
其中 qj 是已知的常数（因为 pj 已知）。
所以问题转化为：
已知数组 q1,q2,…,qm，找一个整数 k 使
最小。
这是经典问题：最小绝对偏差和，当 k 取 q 的中位数时，和最小。
因此：
先找出所有
'1'的位置 p1,p2,…,pm。计算 qj=pj−(j−1)。
对 q 数组排序，取中位数
。
计算
，这就是最小操作次数。
正解：
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; string s; cin >> n >> s; // 收集所有1的位置 vector<int> pos; for (int i = 0; i < n; i++) { if (s[i] == '1') { pos.push_back(i + 1); // 转成1-based } } int cnt = pos.size(); // 1的个数 // 计算q数组 vector<long long> q(cnt); for (int i = 0; i < cnt; i++) { q[i] = pos[i] - i; // 公式推导：q_j = p_j - (j-1) 在代码中简化为 pos[i] - i } // 排序取中位数 sort(q.begin(), q.end()); long long mid = q[cnt / 2]; // 计算总距离 long long ans = 0; for (auto x : q) { ans += abs(x - mid); } cout << ans << endl; return 0; }