题解 | F题

按照B站上讲的题解来就是了，但是我不明白的一点，当bad.size<=6时，我不交换（好，好）的时候，就过不了。和B站讲的有点不一样

#include<bits/stdc++.h>

using namespace std;

template<class T>
void read(T &num) {
    T x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    num = x * f;
}

template<typename T, typename ...Arg>
void read(T &x, Arg &...arg) {
    read(x), read(arg...);
}

#define all(v) v.begin(),v.end()
#define eu(v) v.erase(unique(all(v)), v.end())

int n, k;

bool check(vector<int> &v) {
    for(int i = 0; i < n; ++i) {
        int num1 = v[i];
        int num2 = v[(i + 1) % n];
        if(abs(num1 - num2) > k)return false;
    }
    return true;
}

void solve() {
    read(n, k);
    vector<int> v(n), st(n, 0);
    for(int i = 0; i < n; ++i)read(v[i]);

    vector<int> bad, good;
    for(int i = 0; i < n; ++i) {
        int num1 = v[i];
        int num2 = v[(i + 1) % n];
        if(abs(num1 - num2) > k) {
            bad.emplace_back(i);
            bad.emplace_back((i + 1) % n);
            st[i] = st[(i + 1) % n] = 1;
        }
    }
    sort(all(bad)), eu(bad);
    for(int i = 0; i < n; ++i)
        if(!st[i])good.emplace_back(i);

    if(bad.empty()) {
        ::printf("0\n");
        return;
    }
    else if(bad.size() > 12) {
        ::printf("-1\n");
        return;
    }
    else if(bad.size() > 6) {
        vector<int> back = v;
        for(auto i1 : bad)
            for(auto i2 : bad)
                for(auto i3 : bad)
                    for(auto i4 : bad) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }

        for(auto i1 : bad)
            for(auto i2 : bad)
                for(auto i3 : bad)
                    for(auto i4 : good) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }
    }
    else {
        vector<int> back = v;

        for(auto i1 : bad)
            for(auto i2 : bad)
                for(auto i3 : bad)
                    for(auto i4 : bad) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }

        for(auto i1 : bad)
            for(auto i2 : bad)
                for(auto i3 : bad)
                    for(auto i4 : good) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }

        for(auto i1 : bad)
            for(auto i2 : good)
                for(auto i3 : bad)
                    for(auto i4 : good) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }

        for(auto i1 : good)
            for(auto i2 : good)
                for(auto i3 : bad)
                    for(auto i4 : good) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }

        for(auto i1 : good)
            for(auto i2 : good)
                for(auto i3 : bad)
                    for(auto i4 : bad) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }

        for(auto i1 : good)
            for(auto i2 : good)
                for(auto i3 : good)
                    for(auto i4 : good) {
                        swap(v[i1], v[i2]), swap(v[i3], v[i4]);
                        if(check(v)) {
                            ::printf("2\n");
                            ::printf("%d %d\n%d %d\n", i1 + 1, i2 + 1, i3 + 1, i4 + 1);
                            return;
                        }
                        v = back;
                    }
    }

    ::printf("-1\n");
}

signed main() {
#ifndef ONLINE_JUDGE
    setbuf(stdout, nullptr);
    freopen("../input.txt", "r", stdin);
#endif
    int T = 1;
    read(T);
    while(T--)solve();
    return 0;
}