Incomplete Implementation 详解

拿个沙发
此题是典型的思维题，且 “思维容易，实现难” 主要是实现比较难想到。

代码如下，具体细节通过注释给出
其中，c 数组记录选中数在 a 中的下标，d 数组记录选中数的值，c 和 d 的配合可以对选出来的离散集合进行排序，通过排序后的结果，依次修改 a 数组和 b 数组。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int a[100009], b[100009], n;

int c[100009], d[100009], vis[100009];

void fu(int l, int r){
    int tot = 0;  memset(vis, 0, sizeof(vis));
    ///   确保前四分之一的数在集合中
    for(int i = l; i <= r; i ++){
        if(!vis[i]) c[++ tot] = i, vis[i] ++;
        if(!vis[b[i]]) c[++ tot] = b[i], vis[b[i]] ++;
    }
    ///   如果不够二分之一的数， 则补足缺少的部分
    for(int i = r + 1; tot < n / 2; i ++)
        if(!vis[i]) c[++ tot] = i;
    ///   打印答案
    for(int i = 1; i <= n / 2; i ++) {
        if(i != 1) cout <<  ' ';
        cout << c[i];
    }   cout << endl;
    ///   利用 c 、d 数组对保存临时值，对离散的集合排序
    for(int i = 1; i <= tot; i ++)
        d[i] = a[c[i]];
    sort(c + 1, c + n / 2 + 1);
    sort(d + 1, d + 1 + tot);
    for(int i = 1; i <= n / 2; i ++)
        a[c[i]] = d[i];
    ///   重置修改后的 b 数组
    for(int i = 1; i <= n; i ++)
        b[a[i]] = i;
}
int main(){
    cin >> n;
    for(int i = 1; i <= n;i ++) {
        cin >> a[i];
        b[a[i]] = i;
    }
    cout << 3 << endl;      /// 三步必定可以成功，先排前四分之一，再排第二个四分之一，最后排最后二分之一
    fu(1, n / 4);
    fu(n / 4 + 1, n / 2);
    for(int i = n / 2 + 1; i <= n; i ++) {
        if(i != n / 2 + 1) cout << ' ';
        cout << i;
    }
    return 0;
}

最后欢迎大家给我指出值得改进的地方。