2024 天梯赛——工业园区建设题解

思路

将点 $i$ 视为固定点， 点 $j$ 视为灵活点，其中 $s_i=1$，$s_j=0$。维护四个队列，其中 $q_0$ 和 $q_1$ 分别维护还没有被选用的固定点 和 灵活点，$Q_0$ 和 $Q_1$ 分别维护 正在被使用的固定点 和 灵活点。此外，维护一个 rnum 表示当前位置右边（包含当前位置）正在被使用的固定点和灵活点的总数，维护 dis 表示当前的最优答案.

依次求解位置 i = 0, 1, …, n - 1 情况下的最优解，并动态更新队列和rnum，在此基础上探索四个队列的一些基本性质:
记 $x$ 属于 $q_0\cup q_1$ 的点 和 $y$ 属于 $Q_0\cup Q_1$ 的点

1. $Q_0$ 和 $Q_1$ 的交集为空 且并集为当前位置的最优解.
2. 每次更新完队列后，对于任意的 $x$，均有 $x>i$. 因为当我们扫描到位置 $i$ 时，点$x=i$ 必定属于最优解，因此点$i$ 必定已被加入 $Q_0$ 或者 $Q_1$.
3. m i n { x } > m a x { y } min \{x\} > max \{y\} min{x}>max{y}. 因为当 存在 $x_0<y_0$ 时，那么 $i<x_0<y_0$，将 $x_0$ 替换 $y_0$会更优.

如何维护上述数据？

1. 当扫描到 i 时，如果点 i - 1 属于上一个位置的最优解，那么 rnum -= 1 且 dis -= (2 * rnum - k).

2. 选用 $q_0$ 和 $q_1$ 中的最左端的点 x_left，判断是否允许用来替换 $Q_0$ 和 $Q_1$ 中的最左端的点 y_left。显然，x_left >= i 且 x_left > y_left。当 x_left - i <= i - y_left时，将 x_left 替换 y_left 并更新 rnum 和 dis. 此外，当 x_left 来自 $q_0$ 时，它允许替换$Q_0$ 和 $Q_1$中的点. 当 x_left 来自$q_1$ 且 $Q_1$的大小 < m 时，它允许替换$Q_0$ 和 $Q_1$ 中的点，否则只能替换 $Q_1$中的点. 循环执行上述步骤，直到条件不能满足.

显然，每一轮替换后，确保$Q_0$ 和 $Q_1$ 更新为最优解. 此外，当 $y$ 在位置 i 被抛弃后，它不可能再成为 位置 j (j > i)的最优解.

时间复杂度：$O(n)$

Code

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;void solve() {int n, m, k;std::cin>>n>>m>>k;std::string s;std::cin>>s;std::vector<i64>ans(n);std::vector<int>vis(n);std::array<std::queue<int>, 2> q, Q;for(int i = 0;i < n;i++) {if(s[i] == '1') {q[0].push(i);} else {q[1].push(i);}}m = std::min(m, (int)q[1].size());i64 dis = 0, rnum = k;for(int i = 0;i < k;i++) {if(!q[0].empty() && (!q[1].empty() && Q[1].size() < m)) {if(q[0].front() < q[1].front()) {Q[0].push(q[0].front());dis += q[0].front();vis[q[0].front()] = 1;q[0].pop();} else {Q[1].push(q[1].front());dis += q[1].front();vis[q[1].front()] = 1;q[1].pop();}} else if(!q[0].empty()) {Q[0].push(q[0].front());dis += q[0].front();vis[q[0].front()] = 1;q[0].pop();} else {assert(Q[1].size() < k);Q[1].push(q[1].front());dis += q[1].front();vis[q[1].front()] = 1;q[1].pop();}}ans[0] = dis;auto Oper = [&] (int i, int j, int p)->bool {assert(!q[i].empty());assert(!Q[j].empty());assert(q[i].front() >= p);if(q[i].front() - p > p - Q[j].front()) {return false;}assert(Q[j].front() <= p);vis[Q[j].front()] = 0;dis -= (p - Q[j].front());Q[j].pop();dis += (q[i].front() - p);vis[q[i].front()] = 1;rnum += 1;Q[i].push(q[i].front());q[i].pop();return true;};auto calc = [&](int op, int i) ->bool{bool res = false;if(op == 0 || Q[1].size() < m) {if(!Q[0].empty() && (!Q[1].empty() && m)) {int cs = (Q[0].front() < Q[1].front()?0 : 1);res = Oper(op, cs, i);} else if(!Q[0].empty()) {res = Oper(op, 0, i);} else if(!Q[1].empty()){res = Oper(op, 1, i);}} else if(m > 0){res = Oper(1, 1, i);}return res;};for(int i = 1;i < n;i++) {if(vis[i - 1] == 1) {rnum -= 1;}//  在当前点集的作用下，dis 的更新方式如下：dis -= rnum;dis += (k - rnum);bool ok = true;while((!q[0].empty() || !q[1].empty()) && ok) {ok = false;int cs = -1;if(!q[0].empty() && (!q[1].empty() && m)) {cs = (q[0].front() < q[1].front()?0 : 1);} else if(!q[0].empty()) {cs = 0;} else if(!q[1].empty() && m){cs = 1;}if(cs != -1) {ok = calc(cs, i);}}ok = true;while(!q[0].empty() && ok) {ok = false;if(!Q[0].empty() && !Q[1].empty()) {int cs = (Q[0].front() < Q[1].front()?0 : 1);ok = Oper(0, cs, i);} else if(!Q[0].empty()) {ok = Oper(0, 0, i);} else if(!Q[1].empty()){ok = Oper(0, 1, i);}}ans[i] = dis;}for(int i = 0;i < n;i++) {std::cout<<ans[i];if(i + 1 < n) {std::cout<<" ";}}
} int main(){std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;std::cin>>t;while(t--) {solve();if(t) {std::cout<<"\n";}}return 0;
}