[PA2021] Wystawa
牛逼啊喔趣。
题意
给定长度为 \(n\) 的序列 \(a, b\)。
你需要构造一个序列 \(c\)，构造方法为：
- 选择 \(k\) 个 \(i\)，令 \(c_i \leftarrow a_i\)。
- 对于其他 \(i\)，令 \(c_i \leftarrow b_i\)。
求序列 \(c\) 的最大子段和的最小值，并给出一种方案。
Sol
感觉最小值很难直接做，我们可以考虑判断是否存在方案满足最大子段和 \(\le x\)。
然后会发现如果 \(a_i < b_i\) 那么这时选 \(i\) 一定不劣。假如有 \(K\) 个位置满足这样的条件。
那么首先钦定 \(K \ge k\)，否则可以交换原本的 \(a,b\) 序列，同时 \(k \leftarrow n - k,K\leftarrow n-K\)。
所以我们可以设想先选了 \(K\) 个位置，使得这时的最大子段和比所有方案都还要小。所以现在要解决的就是我们需要把 \(K-k\) 个位置从原本选择的 \(a_i\) 换成 \(b_i\)，使得最大子段和最小。
策略应是，尽量少的损失下使被换成 \(b_i\) 的 \(a_i\) 个数到达 \(K-k\) 个。
所以如果加上这个位置后维护的 \(c\) 的子段和 \(s\) 变成负数，可以发现其实应该尽量多地压榨这个出现的负数（因为在指针跳到下一个位置前为了保持最大会使 \(s \leftarrow 0\)）。
当然，如果 \(s>x\) 那么直接返回 \(F\)。
所以考虑尽量多地将前面的一些 \(a_i\) 变成 \(b_i\)。这样一定不会更劣。所以我们考虑维护一个数据结构保存 \(a_i\) 的贡献。贡献为 \(b_i-a_i\)。那么实际上我们就是将 \(b_i-a_i\) 最小的数通过这个负数给消掉。而每次我们让一个原本 \(c_i=a_i\) 的位置 \(c_i\leftarrow b_i\)，会使得 \(s\leftarrow s+val\) 变大，同时我们成功地删去了 \(K-k\) 中的一个位置。如果 \(s\) 在下一个位置发生变化时则不能继续压榨了，结束这次压榨，同时原本下一个准备压榨 \(s\) 的贡献位置 \(i\) 的贡献应该增加 \(s\)，因为这个位置下一次被变为 \(b_i\) 时贡献必须要经过这个 \(s\)。就会被减掉一些值。因为 \(s<0\) 所以不用担心下次拿出的贡献少考虑什么东西，因为如果要拿当前可以使用的贡献中的其他一部分就必须先使用这个位置 \(i\)。而加上这个 \(i\) 的贡献之后这段又会变成非负数。所以归纳一下，正确性是有的。
但是因为 \(c_i\leftarrow b_i\) 导致了最大子段和 \(>x\) 的情况上述的策略是没有考虑到的。所以我们可以考虑更进一步，考虑再记录一个 \(s_b\) 表示能选 \(b\) 时尽量选 \(b\) 的最大子段和。如果某个时刻 \(s_b > x\)，那么考虑就要将前边的一些可以选 \(a_i\) 或 \(b_i\) 的不定位置强制选择 \(a_i\)。
仍然考虑尽量压榨，尽量少地选择强制为 \(a_i\) 的位置。所以我们应该选贡献尽量大的位置。考虑仍然在上述同一个数据结构中选择最大贡献的位置并使其强制选择 \(a_i\)（实际上相当于将 \(i\) 直接从数据结构中删去而不计入在删去的 \(K-k\) 个数中）。如果 \(s_b\le x\)，那么停止选择。
当然最终不能忘记将还没有选择的一些位置。这时仍然先选小的贡献，意义是删去 \(K-k\) 中的一个位置，同时让 \(s\) 加上贡献 \(val\)。
最后的判断条件是 \(K-k\) 个位置全部完成替换且 \(s\le x\)。可以发现不会多替换了。如果存在某个子段的 \(s>x\)，则应当已经提前退出了。
Code
跟 Luogu 上的一篇题解很像，因为我是照着看代码才看懂的，所以实现也很类似。
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct cont {
int val, pos;
cont (int VAL = 0, int POS = 0){
val = VAL;
pos = POS;
}
bool operator < (const cont &oth) const {
if (val == oth.val)
return pos < oth.pos;
return val < oth.val;
}
};
int n, k, K, a[100005], b[100005];
char ans[100005];
set < cont > st;
bool is_swap;
bool Cmp (int A, int B){
if (is_swap)
return A <= B;
return A < B;
}
bool Check (int lim){
int s = 0, sb = 0, rest = K - k;
st.clear ();
for (int i = 1;i <= n;++ i){
if (Cmp (a[i], b[i])){
s += a[i];
ans[i] = 'A';
st.insert (cont (b[i] - a[i], i));
} else {
s += b[i];
ans[i] = 'B';
}
if (s > lim)
return false;
int v, p;
while (rest > 0 && s < 0 && ! st.empty ()){
set < cont > :: iterator it = st.begin ();
v = (*it).val, p = (*it).pos;
if (s + v <= 0){
-- rest;
s += v;
ans[p] = 'B';
st.erase (it);
} else {
v += s;
st.erase (it);
st.insert (cont (v, p));
break;
}
}
s = max (s, 0ll);
sb = max (sb + b[i], 0ll);
while (sb > lim && ! st.empty ()){
set < cont > :: reverse_iterator it = st.rbegin ();
v = (*it).val;
p = (*it).pos;
sb -= v;
st.erase (cont (v, p));
}
if (sb > lim)
return false;
}
while (rest > 0 && ! st.empty ()){
set < cont > :: iterator it = st.begin ();
-- rest;
int v = (*it).val, p = (*it).pos;
s += v;
ans[p] = 'B';
st.erase (it);
}
return rest == 0 && s <= lim;
}
signed main (){
scanf ("%lld%lld", &n, &k);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &a[i]);
for (int i = 1;i <= n;++ i)
scanf ("%lld", &b[i]);
for (int i = 1;i <= n;++ i)
if (a[i] < b[i])
++ K;
if (k > K){
k = n - k;
K = n - K;
is_swap = true;
for (int i = 1;i <= n;++ i)
swap (a[i], b[i]);
}
int L = 0, R = 0x3f3f3f3f3f3f3fll, mid;
while (L < R){
mid = (L + R) >> 1;
if (Check (mid))
R = mid;
else
L = mid + 1;
}
Check (L);
printf ("%lld\n", L);
for (int i = 1;i <= n;++ i)
putchar (((ans[i] - 'A') ^ (int) is_swap) + 'A');
return 0;
}