【每日一题】CF1607 D. Blue-Red Permutation | 贪心 | 简单

题目内容

原题链接

给定一个长度为 $n$ 的数组 $a$ ，以及一个长度为 $n$ 的字符串 $s$ ，字符要么为 'B' 要么为 'R'。

一次操作中，可以选择一个下标 $i$ ：

• 如果 $s_i$ 为 'B' ，可以将 $a_i$ 减少 $1$
• 如果 $s_i$ 为 'R' ，可以将 $a_i$ 加上 $1$

执行若干次操作，问是否可以将数组 $a$ 操作成一个 $1-n$ 的排列。

数据范围

• $3\le n\le 2\cdot 10^5$
• $1\le a_i\le 10^9$

题解

对于下标 $i$

• 如果 $s_i$ 为 'B' ，那么小于等于 $a_i$ 的值都可以达到
  • 对于小于等于 $0$ 的 $a_i$ ，其可达值均不会在 $1-n$ 之间，此时答案必然为 NO
  • 排除上面的情况，我们可以将 $a_i$ 替换为 $[1,a_i]$ 中的任意一个数
• 如果 $s_i$ 为 'R' ，那么大于等于 $a_i$ 的值都可以达到
  • 对于大于等于 $n+1$ 的 $a_i$ ，其可达值均不会在 $1-n$ 之间，此时答案必然为 NO
  • 排除上面的情况，我们可以将 $a_i$ 替换为 $[a_i,n]$ 中的任意一个数

所以我们最终预处理出每个数可以变成 $[1,a_i]$ 或者 $[a_i,n]$

贪心的考虑

• 对于 $[1,a_i]$ 的区间，我们先考虑 $a_i$ 更小的数，依次将对应的数变成 $1,2,\cdots ,x$
• 对于 $[a_i,n]$ 的区间，我们也先考虑 $a_i$ 更小的数，依次将对应的数变成 $x+1,x+2,\cdots ,n$

如果最终我们不能将每个数都拿到，则说明无法操作为一个排列。

时间复杂度：$O(n\log n)$ ，瓶颈在于排序

代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    string s;
    cin >> s;

    vector<int> st, ed;
    for (int i = 0; i < n; ++i) {
        if (s[i] == 'B') {
            if (a[i] <= 0) {
                cout << "NO\n";
                return;
            }
            // 1 ~ a[i]
            st.push_back(a[i]);
        } else {
            if (a[i] > n) {
                cout << "NO\n";
                return;
            }
            // a[i] ~ n
            if (a[i] == 1) st.push_back(n);
            else ed.push_back(a[i]);
        }
    }

    sort(st.begin(), st.end());
    sort(ed.begin(), ed.end());
    // 先看 st 能拯救多少个
    int cur = 1;
    for (int u: st) {
        if (u >= cur) cur += 1;
        else break;
    }

    for (int u: ed) {
        if (u <= cur) cur += 1;
        else break;
    }

    if (cur > n) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

代码分析

在上述代码实现中，我们做了两部分考虑：

• 以 $[1,a_i]$ 这样开头的，那么我们将其加入 st 中
• 以 $[a_i,n]$ 这样开头的，那么我们将其加入 ed 中
• 对于 $[1,n]$ 的这个既属于 $[1,a_i]$ 也属于 $[a_i,n]$ 的，我们将其加入了 st ，是否有问题呢？

我们来思考下将其加入到 st 和 ed 的情况：

• 加入到 st ，我们优先考虑 $a_i$ 小的。
• 先操作 $[1,a_i]$ 的，其中 $a_i=n$ 对应的 $[1,n]$ 是在这部分最后的，然后是 $[a_i,n]$
• 加入到 ed ，我们优先考虑 $a_i$ 小的。先操作到 $[1,a_i]$ 的，然后操作 $[a_i,n]$ ，对于 $[a_i,n]$ 这部分先考虑 $[1,n]$ ，再考虑 $a_i>1$ 的 $[a_i,n]$ 。

因此加入到哪部分都是一样的，$[1,n]$ 总是在最中间被操作。