题解 | #小红出千#

题目的意思是将这n张牌修改成一个顺子，求最小的操作次数

修改后的顺子一定是[left, left + 1, left + 2, ... , right]，其中right - left + 1 = n, 也就是长度为n

那么最优的方法就是依次枚举每一个a[i]为左边界left，然后看有多少个元素在[a[i], a[i] + n - 1]

所以首先得对a[]数组进行从小到大的排序并且去重

sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());

然后依次枚举每一个a[i]:

ans表示的是最小需要操作的次数，初始化n，表示最坏情况将n个数全部操作1次

以a[i]为左边界，那么有边界就是a[i] + n - 1, 用upper_bound来找到第一个大于a[i] + n - 1的位置，那么next_pos - i 表示在区间[a[i], a[i] + n - 1]包含了多少个a[]中的元素，这些元素在区间中那么就不需要修改，所以n - sum就表示需要修改的数目，以此来更新操作次数的最小值即ans

pos表示存储的左边界

int ans = n, pos = 0;
for(int i = 0; i < (int)a.size(); i ++){
    int next_pos = upper_bound(a.begin(), a.end(), a[i] + n - 1) - a.begin();
    int sum = next_pos - i;
    if(n - sum < ans){
        ans = n - sum;
        pos = a[i];
    }
}
cout << ans << endl;

剩下的就是求哪些元素需要操作以及操作到哪个位置，并不需要求具体哪些元素需要操作，只需要求需要操作的位置以及操作后的位置

既然现在左边界已经有了，那么我们就可以得知哪些元素在这个里面，但是不知道这些元素在原来a[]数组里面的位置，所以还得用map一开始存储数组元素的下标位置

int n; cin >> n;
vector<int> a(n);
map<int, int> ma;
for(int i = 0; i < n; i ++){
    cin >> a[i];
    ma[a[i]] = i;
}

煎蛋来说：有两个数组

第一个数组是一开始的a数组，第二个数组是题目需要的顺子数组

现在我们确定了a[i]为顺子的左边界

vis1数组表示的是顺子数组里面的填充情况，如果为1表示该位置不需要操作，a数组里面存在一个值直接放在这个位置就可以了，如果为0则表示需要操作

vis2数组表示原来的a数组下标的使用情况，如果为1则表示该位置的元素直接放在顺子数组里面了，而为0则表示这个值不在顺子数组里面，我需要对其进行操作

pos是顺子的左边界即之前的a[i], now_num = pos + i 则是顺子数组里面的每一个元素

如果ma.count(now_num)则表示now_num既在原来的a数组中存在也在顺子数组中存在.....

vector<int> vis1(n + 1), vis2(n + 1);
for(int i = 0; i < n; i ++){
    int now_num = pos + i;
    if(ma.count(now_num)){
        vis1[i] = 1;
        vis2[ma[now_num]] = 1;
    }
}

最后就是输出操作的位置：

int now = pos;
for(int i = 0; i < n; i ++){
    while(vis1[now - pos]) now ++;
    if(vis2[i]) continue;
    else cout << i + 1 << " " << now ++ << endl;
}

总代码：

#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


signed main(){
    HelloWorld;
    
    int n; cin >> n;
    vector<int> a(n);
    map<int, int> ma;
    for(int i = 0; i < n; i ++){
        cin >> a[i];
        ma[a[i]] = i;
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    int ans = n, pos = 0;
    for(int i = 0; i < (int)a.size(); i ++){
        int next_pos = upper_bound(a.begin(), a.end(), a[i] + n - 1) - a.begin();
        int sum = next_pos - i;
        if(n - sum < ans){
            ans = n - sum;
            pos = a[i];
        }
    }
    cout << ans << endl;
    vector<int> vis1(n + 1), vis2(n + 1);
    for(int i = 0; i < n; i ++){
        int now_num = pos + i;
        if(ma.count(now_num)){
            vis1[i] = 1;
            vis2[ma[now_num]] = 1;
        }
    }
    int now = pos;
    for(int i = 0; i < n; i ++){
        while(vis1[now - pos]) now ++;
        if(vis2[i]) continue;
        else cout << i + 1 << " " << now ++ << endl;
    }
    return 0;
}