只有我把题意看错了。
查看原帖
只有我把题意看错了。
524191
Man_CCNU楼主2021/12/8 10:37

**只有我看错题意了?我理解的是只要符合交换规则可以交换任意次,并且从任意可交换的位置开始,比如样例 6 5 3 1 6 0 3 1 6 0 3 1 6 0 最大匹配数应该是6

#include<iostream>
#include<cstring>

using namespace std;

const int N = 1e3 + 10;
int a[N],tem[N], n, x,res;
bool f[N];

bool judge(int i)
{
    if (a[i] <= x && f[i] || a[i] > x && !f[i]) return true;

    return false;
}
bool pro(int i)
{
    memcpy(tem, a, sizeof a);
    if (f[i]) {
        int index_ = -1;
        for (int j = i + 1; j <= n; j++) {
            if (a[j] <= x) { index_ = j; break; }
        }
        if (index_ == -1) return false;
        for (int k = index_; k > i; k--) {
            if (f[k] != f[k - 1]) swap(tem[k], tem[k - 1]);
            else return false;
        }
    }
    else {
        int index_ = -1;
        for (int j = i + 1; j <= n; j++) {
            if (a[j] > x) { index_ = j; break; }
        }
        if (index_ == -1) return false;
        for (int k = index_; k > i; k--) {
            if (f[k] != f[k - 1]) swap(tem[k], tem[k - 1]);
            else return false;
        }
    }

    return true;
}
int main()
{
    cin >> n >> x;
    for (int i = 1; i <= n; i++) cin >> a[i] >> f[i];
    for (int i = 1; i <= n; i++) {
        if (judge(i)) {
            res++;
            continue;
        }
        else {
            if (i == n) break;
            swap(a[i], a[i + 1]);
            if (judge(i)) {
                res++;
                continue;
            }
            swap(a[i], a[i + 1]);
            if (!pro(i)) continue;
            else {
                memcpy(a, tem, sizeof tem);
                res++;
            }
        }
    }
    cout << res << endl;

    return 0;
}

**

2021/12/8 10:37
加载中...