Educational Codeforces Round 99 (Rated for Div. 2) - D. Sequence and Swaps

Solost

2023 年 04 月 16 日

174 次浏览

暂无评论

1330字数

题目题解

## 题目

![image(1).png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F16%2Fimage%281%29.png)

## 题目链接

[链接](https://codeforces.com/problemset/problem/1455/D)

## 题目大意

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

## 题解

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

```cpp
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必然比那个数还大，所以就算往后遍历也没用。所以我们只用遍历到最后一个无序点即可

```cpp
#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;
}
```

最后修改：2023 年 04 月 16 日