题目描述

难度分:$2600$

输入$n(1 \leq n \leq 2 \times 10^5)$和$n$个数对$(a_i,b_i)$，保证这$2n$个数在$[1,2n]$中且互不相同。

有$n$张牌，第$i$张牌的正面是$a_i$，反面是$b_i$。

你可以随意排列这些牌，也可以翻转牌（交换$a_i$和$b_i$）。

要使$a$是递增的，$b$是递减的，最少要翻多少张牌？如果无法做到，输出$-1$。

输入样例$1$

5
3 10
6 4
1 9
5 8
2 7

输出样例$1$

2

输入样例$2$

2
1 2
3 4

输出样例$2$

-1

输入样例$3$

3
1 2
3 6
4 5

输出样例$3$

-1

算法

构造

完全不会做，参考灵佬的构造方法。

举例说明

从写有$1$的牌开始。这张牌要么在最左边（$1$在上），要么在最右边（$1$在下）。不妨设其在最左边。

假设$1$反面的数字是$8$。
现在牌是这样放的（下划线表示空位）：

1 _ _ _ _
8 _ _ _ _

比$8$大的那些数应该在哪？假如最大的数是$10$，那么$10$只能在最右边且朝上。$9$也同理。假设$10$的反面的数字是$3$，$9$的反面的数字是$4$。现在牌是这样放的：

1 _ _ 9 10
8 _ _ 4 3

比$3$小的数（$2$）应该在哪？只能在$1$右边且朝上。假设其反面为$7$。现在牌是这样放的：

1 2 _ 9 10
8 7 _ 4 3

不断重复上述过程，直到没有必须放在左/右的牌。

上述过程中，如果放了$x$张牌，其中翻转了$k$张牌，那么不翻转这$k$张牌，改为翻转另外$x-k$张牌，也可以满足题目要求，所以每一轮把$min(k, x-k)$累加在答案上。

如果发现没有必须放在左/右的牌，那么剩余问题变成一个规模更小的子问题解决。最后判断两个数组是否有序即可（说得容易，其实代码也不是很好写，还需要好好学习代码）。

复杂度分析

时间复杂度

整个过程就相当于把$2n$个数填在$O(n)$级别的位置上，因此时间复杂度为$O(n)$。

空间复杂度

参考代码，其中所有的辅助数组都是线性空间，因此额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
int n;

void solve() {
    cin >> n;
    int ans = 0;
    vector<int> to(2 * n + 1), is_back(2 * n + 1);
    vector<PII> ps(n);
    for(int i = 0; i < n; ++i) {
        cin >> ps[i].first >> ps[i].second;
        is_back[ps[i].second] = 1;
        to[ps[i].first] = ps[i].second;
        to[ps[i].second] = ps[i].first;
    }
    vector<int> a(n), b(n);
    int al = 0, ar = n - 1, bl = 0, br = n - 1;
    vector<bool> vis(2 * n + 2);
    int mn = 1, mx = 2 * n;
    while(true) {
        while(vis[mn]) ++mn;
        if(mn > 2 * n) break;
        vector<int> cnt(2, 0);
        int t = mn;
        while(true) {
            int last = 0;
            for(; mn <= t; ++mn) {
                if(vis[mn]) continue;
                cnt[is_back[mn]]++;
                vis[mn] = true;
                a[al++] = mn;
                last = to[mn];
                vis[last] = true;
                b[bl++] = last;
            }
            if(last == 0) break;
            t = last;
            last = 0;
            for(; mx >= t; --mx) {
                if(vis[mx]) continue;
                cnt[is_back[mx]]++;
                vis[mx] = true;
                a[ar--] = mx;
                last = to[mx];
                vis[last] = true;
                b[br--] = last;
            }
            if(last == 0) break;
            t = last;
        }
        ans += min(cnt[0], cnt[1]);
    }
    reverse(b.begin(), b.end());
    if(!is_sorted(a.begin(), a.end()) || !is_sorted(b.begin(), b.end())) {
        cout << -1 << endl;
        return;
    }
    cout << ans << endl;
}

int main() {
    solve();
    return 0;
}