CF1707A

wzy2021 · 2022-07-19 23:44:55 · 题解

首先用一张图引出思路，

由上图的调整方法可以知道，存在一种最优方案，

使得在此方案中第一个让 Doremy 的 IQ 减 1 的比赛 i，比赛 j(i \leq j \leq n) 都选择了。

所以从后往前考虑，后 i 个全选所需要的最小代价。

若当前考虑的 i 所需要的代价等于 q (Doremy 的原本 IQ)，

那么答案的组成有两部分：

#include <cstdio>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int a[N], vis[N];

int main() {
    int T; scanf ("%d", &T);
    while (T--){
        int n, q; scanf ("%d%d", &n, &q);
        for (int i = 1; i <= n; ++i) scanf ("%d", &a[i]);
        for (int i = 1; i <= n; ++i) vis[i] = 0;
        int t = 0, now = n;
        while (now >= 1 && t < q) {
            if (a[now] > t) ++t;
            vis[now] = 1; now --;
        }
        for (int i = now; i >= 1; --i) {
            if (a[i] <= q) vis[i] = 1;
        }
        for (int i = 1; i <= n; ++i) printf ("%d", vis[i]);
        printf ("\n");
    }
    return 0;
}