0%

CodeForce 1311 B：WeirdSort

发表于 分类于 Valine：

限定了交换位置的排序

题目链接

https://codeforces.com/contest/1311/problem/B

题意

一个乱序的数组\(a_1,a_2,a_3,...,a_n\)。想要将排成非递减序列。但是限制了只有某些位置可以交换：给定数组\(p_1,p_2,p_3,...,p_m\)，\(p_i\)表示\(a[p_i]\)可以和\(a[p_i + 1]\)进行交换。给定n、m，以及数组a[]、p[]，问在p数组的限制条件下，是否能将其排成非递减序列。

数据范围：\(1\le m<n\le 100\)

题解

我的复杂做法

排序过程就是移动元素的过程——也就是不断交换的过程。乱序数组的最终排序是唯一的，因此对于每个元素，如果在前往其目标位置的路上，都能连续进行交换，则排序是可行的。

在下面的叙述中，为简便起见，若数组中某个元素能够到达最终的位置，则称这个元素为可排序的。

首先将p数组排序。再设置一个temp数组，存储排序后的a数组。再对temp数组的每个元素(设下标为i)，依次查找其在a数组的原始位置j(不妨设i < j 。因为j >i同理；i = j则无需移动)，若p数组存在一组连续的子序列为i, i + 1, ..., j - 1。则对于此元素temp[i]是可排序的。只有当所有元素是可排序的，整个数组才是可排序的。

这里需要设置一个visit数组，标记已经对应过的a[i]，用来应对多个相等元素的情况。

另外，考虑 多个相等元素的情况时，无需担心相等元素的之间的不同的配对方案对结果的影响。因为在上述算法中，每轮处理的temp[i]，都是所有未被配对的temp数组元素最左边的元素；每次查找的a[j]，也都是所有未被配对的a数组元素最左边的元素。

  • 如果在某一轮中，查找到的a[j]无法到达temp[i]
    • 若j < i。则a[j]肯定也无法到达temp[i]之后的与temp[i]相等的元素；结果为NO没毛病。
    • 若i < j。则a[j]之后的所有与a[j]相等的元素，都无法到达temp[i]的位置。结果为NO也没毛病。
  • 如果在某一轮中，查找到的a[j]可以到达temp[i]，并直接作为最终配对
    • 若后续所有与a[j]相等的元素都找到了可到达的元素，则此配对合理；
    • 若后续存在temp[k] = temp[i] (k >i)，没有元素可到达temp[k]，则位于所有可能的a数组元素最左边的a[j]，也不可能到达temp[k]。
    • 换句话说，a[j]和temp[i]配对，不影响任何一种结果的判断。

更优美的做法

这里参考了blb的做法）

我们把目光聚焦到p数组。升序排序后的p数组，如同把a数组划定了若干个区域。p数组任意的连续段，就是划定了一个“自由排序”的区域。比方说， \(p_i, p_{i +1}, p_{i+2},...,p_{j - 1},p_j\)是一段连续段。则说明\(a[p_i]\)到\(a[p_j+1]\)这一段可以做局部排序。注意单独的\(p_k\)也是一个连续段，说明\(a[p_k]\)到\(a[p_k+1]\)可以做局部排序。

那么，除了上述定义的可局部排序之外的区域，都无法进行任何移动。因此，只需找出这些可排序的区域，应用sort函数进行排序即可。最终检查a数组是否为非降序即可。

AC代码

更优美的做法：

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
#include <bits/stdc++.h>

using namespace std;
int a[105];
int p[105];

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i);
        }

        for (int i = 1; i <= m; i++) {
            scanf("%d", p + i);
        }
        sort(p + 1, p + m + 1);
        
        int start = 1;
        int end = 1;
        for (int i = 1; i <= m; i++) {
            if (i == 1) {
                start = p[i];
            }
            
            if (i != 1 && p[i] > p[i - 1] + 1) {
                sort(a + start, a + end + 1);
                start = p[i];
            }

            end = p[i] + 1;
        }

        sort(a + start, a + end + 1); 

        bool res = true;
        for (int i = 1; i < n; i++) {
            if (a[i + 1] < a[i]) {
                res = false ;
                break;
            }
        }

        if (res) printf("YES\n");
        else printf("NO\n");

    }
    return 0;
}

我的WA了一万发终于A了的又臭又长的代码：

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <bits/stdc++.h>

using namespace std;
int a[105];
int p[105];

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        int temp[105];
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            temp[i] = a[i];
        }
        for (int i = 0; i < m; i++) {
            int num;
            cin >> num;
            p[i] = num - 1;
        }

        sort(temp, temp + n);
        sort(p, p + m);

        bool visit[105];  // visit[i] == true 代表下标为i的已经访问
        memset(visit, false, sizeof(visit));
        bool res = true;
        for (int i = 0; i < n; i++) {  // 排序后的列表往后找

            int index = 0;
            bool find = false;

            // 在原数组中查找未被匹配过的元素（有重复元素的情况下）
            for (int j = 0; j < n; j++) {
                if (!visit[j] && temp[i] == a[j]) {
                    visit[j] = true;
                    index = j;
                    break;
                }
            }

            if (index == i) { // 位置相同，不用交换。
                continue;
            }

            int low = min(index, i);
            int high = max(index, i);
            int p_indix_start = -1;
            // 在p数组中查找第一个等于low的元素
            for (int k = 0; k < m; k++) {
                if (p[k] == low) {
                    p_indix_start = k;
                    break;
                }
                if (p[k] > low) {
                    break;
                }
            }

            // 若找到第一个等于low的元素，则查询后续元素是否都是连续递增的(直到high-1)
            if (p_indix_start != -1) {
                for (int k = p_indix_start; k < m; k++) {
                    if (p[k] == high - 1) {
                        find = true;
                        break;
                    }
                    else if (k + 1 >= m || p[k] != p[k + 1] - 1) {
                        find = false;
                        break;
                    }
                }
            }
            // 若没找到第一个等于low的元素，则一定无法到达
            else {
                find = false;
            }
            // 若某元素无法排序，则整个数组必定无法排序
            if (!find) {
                res = false;
                break;
            }
        }
        if (res) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}