题目大意
教主有一栋别墅，所以他雇了 \(N\) 个清洁工，有男有女。
别墅一共有 \(M\) 个房间，现在所有的清洁工在教主面前排成了一排。教主想把这 \(N\) 个清洁工分成 \(M\) 个部分。每个部分在队列中是连续的一段，让后让这 \(M\) 个部分的清洁工分别去打扫这 \(M\) 个房间。
现在教主希望每个部分的清洁工男女个数之差的最大值最小，还想知道分成的这 \(M\) 个部分分别有多少人。
教主知道可能有很多种方案可以满足男女个数之差的最大值最小，所以他想让你输出字典序最小和最大两种情况的方案。
输入
第一行两个正整数 \(N\) 与 \(M\)，用空格分隔。
第二行包含一个长度为 \(N\) 的串，仅由 \(01\) 构成。如果第 \(i\) 个位置为 \(0\) 那么表示当前位置是女生。
输出
两行，每行 \(M\) 个正整数，正整数之间用空格隔开。这 \(M\) 个正整数分别表示你的方案中每个组的人数。
样例
样例输入1
8 3
11001100
样例输出1
1 2 5
5 2 1
提示
对于 \(100\%\) 的数据，有 \(N\le 5000000\)，\(M\le N\) 且 \(M\le 100000\)。
思路
首先这道题字典序最大就相当于是字符串倒过来的字典序最小。
所以我们把问题转化成了给一个字符串，我们要去求字典序最小的方案。
我们可以去求一个前缀和，如果是男生我们就加一，如果是女生就减一。
而我们发现这个前缀和数组中我们最特殊的数就是 \(0\)。因为如果出现了一个 \(0\) 就代表着前面的男生数量和女生数量一样了。
现在我们就可以算出来男生与女生总数量差。
如果总数量差为 \(0\)，我们看如果当前前缀和数组中 \(0\) 的个数大于等于 \(M\) 那么我们的人数差的最大值最小就是 \(0\)（可以理解为我看能不能把整个串分成 \(M\) 个差为 \(0\) 的串，而前缀和中 \(0\) 就代表前若干个人中男生和女生的个数相同）。
如果总数量差不是 \(0\)，那我们要使差的最大值最小就得让这 \(M\) 段的差尽量平均，所以我们就要把这个总数量差去平均分成 \(M\) 份。
那我们现在算出来这个男生数量和女生数量的差的最小值了，我们考虑下一个问题：字典序最小。
字典序最小我们就可以去贪心的去选，看从上一次选完之后的下一个人开始的前若干个人能不能选，如果能选了，我们就选，因为这样我们就可以使前面这些组的人数尽量小（两个串字典序的比较方式是从第一个开始，找到第一个不同的位置，看哪边的小，哪边的字典序就小）。
我们在考虑下一个问题，怎么看从上一次选完之后的下一个人开始的前若干个人能不能选呢？
这里我们分两类看：
-
如果我们这里已经分完 \(M-1\) 段了，那么我们就把最后剩下的那些人算成一段就可以了。
-
如果我们没分完 \(M-1\) 段，那么我们看总男女数量差和前面的男女数量差是否小于等于我们上面算出来的最小值乘上后面还没分的段的个数（这里就相当于我看后边那些段所能接受的差是否能接受我在这里断掉所得的差）。
代码
#include <bits/stdc++.h>
#define db double
#define ll long long
#define ex exit(0)
#define endl "\n"
#define inl inline
#define null NULL
#define pll pair<ll,ll>
#define mkp(a,b) make_pair(a,b)
using namespace std;
ll pre[5000005];
ll ans[5000005];
ll n, m;
void solve(string s) {
ll cnt0 = 0, cnt = 0, shang = 0;
memset(pre, 0, sizeof(pre));
for (int i = 1; i <= n; i++) {
pre[i] = pre[i - 1];
if (s[i] == '1') {
pre[i]++;
} else {
pre[i]--;
}
if (!pre[i]) {
cnt0++;
}
}
ll pj;
if (!pre[n] && cnt0 >= m) {
pj = 0;
} else {
pj = abs(abs(pre[n]) - 1) / m + 1;
}
for (int i = 1; i <= n; i++) {
if (cnt >= m - 1) {
ans[++cnt] = n - i + 1;
return ;
}
if (abs(pre[n] - pre[i]) <= pj * (m - cnt - 1)) {
ans[++cnt] = i - shang;
shang = i;
}
}
}
int main() {
// freopen("villa.in", "r", stdin);
// freopen("villa.out", "w", stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
string s, t;
cin >> s;
t = s;
s = " " + s;
solve(s);
for (int i = 1; i <= m; i++) {
cout << ans[i] << " ";
}
reverse(t.begin(), t.end());
t = " " + t;
solve(t);
cout << endl;
for (int i = m; i >= 1; i--) {
cout << ans[i] << " ";
}
return 0;
}