题目

题目链接

链接

题目大意

这道题给你一个序列，然后然你把他变成一个非严格上升序列，给你一个数x，满足x > a[i]才能换。问你最少多少次操作能把序列变成上升的，如果不能输出-1

题解

看了题解，我的想法是排序，然后判断

for(int i = 1; i <= n; i++){
        cin >> a[i];
        b[i] = a[i];
        if(i > 1 && a[i] < a[i - 1]) f = 0;
    }
    if(f){
        cout << "0\n";
        return;
    }
    b[n + 1] = x;
    sort(b + 1, b + n + 2);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(a[i] <= x){
            if(a[i] != b[i]){
                cout << "-1\n";
                return;
            }
        }
        else{
            if(a[i] != b[i]){
                ans++;
            }
        }
    }

然后发现在胡扯，有的时候多换了。

看了题解的思路，真牛逼，但是冒犯到我了！！！

本题对于代码能力要求并不高，就是看你 ~脑子好不好使~ 能不能想到。

首先，如果有一个a[i] > x但是没有交换，那么到了后面想换的时候a[j] > x但是前面有一个a[i] > x,也就是前面有一个数比当前位置还大。所以，要换就必须得换，如果一个序列本来就有序，那么换了反而增加了次数。所以要换就必须从a[i] > x的时候就开始换。如果后面已经有序，那么换了会增加次数。如果换完最后一个无序点a[j]，那么a[j]必然大于后面某个数，但是换过去的x必然比那个数还大，所以就算往后遍历也没用。所以我们只用遍历到最后一个无序点即可

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 510;

int n, x;
int a[N];

void solve() {
    cin >> n >> x;
    int f = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(i > 1 && a[i] < a[i - 1]) f = i;
    }
    if(!f){
        cout << "0\n";
        return;
    }
    int ans = 0;
    for(int i = 1; i <= f; i++){
        if(a[i] > x) swap(a[i], x), ans++;
    }
    for(int i = 1; i < n; i++){
        if(a[i] > a[i + 1]){
            cout << "-1\n";
            return;
        }
    }
    cout << ans << endl;
}
int main()
{
//    IOS;
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}