HDU 5821 – Ball [思路/贪心]

Link

http://acm.hdu.edu.cn/showproblem.php?pid=5821

Mean

给定两个长度为N的数列A和B,有M次操作,每次可以把Li到Ri段的数字打乱重排,问你能否通过M次操作把A变成B

Analysis

多校场上想了好久没想出来,思路越来越不行了,可能是最近花在ACM上的时间越来越少了吧…

首先能够想到的是如果数列B中有3个2,如果能把A变成B,那么可以定为3个2之间是不交叉交换的。那么这样根据最终的序列就有一个优先级,最后越靠左的数在重排时越靠左,这样我们根据优先级对A序列编号后排序M次,看最终能否变成B即可。

Code

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

const int maxn = 1024;
P A[maxn];
P seg[maxn];
int N, M, B[maxn];
int cnt[maxn];

bool solve() {
    for(int i = 0; i <= N; ++i)
        if(cnt[i] != 0) return false;
    for(int i = 1; i <= N; ++i) {
        for(int j = 1; j <= N; ++j) {
            if(A[j].first != -1) continue;
            if(A[j].second == B[i]) {
                A[j].first = i;
                break;
            }
        }
    }
    for(int i = 1; i <= M; ++i)
        sort(A + seg[i].first, A + seg[i].second + 1);
    for(int i = 1; i <= N; ++i)
        if(A[i].second != B[i])
            return false;
    return true;
}

int main() {
    int T; scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &N, &M);
        memset(cnt, 0, sizeof(cnt));
        memset(A, -1, sizeof(A));
        for(int i = 1; i <= N; ++i) {
            scanf("%d", &A[i].second);
            ++cnt[A[i].second];
        }
        for(int i = 1; i <= N; ++i) {
            scanf("%d", B + i);
            --cnt[B[i]];
        }
        for(int i = 1; i <= M; ++i) {
            scanf("%d%d", &seg[i].first, &seg[i].second);
        }
        puts(solve() ? "Yes" : "No");
    }
    return 0;
}

欢迎留言