当前位置: 代码迷 >> 综合 >> Educational Codeforces Round 99 (Rated for Div. 2) D. Sequence and Swaps(贪心)
  详细解决方案

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

热度:93   发布时间:2023-12-21 00:08:30.0

题目链接:https://codeforc.es/contest/1455/problem/D

You are given a sequence a consisting of n integers a1,a2,…,an, and an integer x. Your task is to make the sequence a sorted (it is considered sorted if the condition a1≤a2≤a3≤?≤an holds).

To make the sequence sorted, you may perform the following operation any number of times you want (possibly zero): choose an integer i such that 1≤i≤n and ai>x, and swap the values of ai and x.

For example, if a=[0,2,3,5,4], x=1, the following sequence of operations is possible:

choose i=2 (it is possible since a2>x), then a=[0,1,3,5,4], x=2;
choose i=3 (it is possible since a3>x), then a=[0,1,2,5,4], x=3;
choose i=4 (it is possible since a4>x), then a=[0,1,2,3,4], x=5.
Calculate the minimum number of operations you have to perform so that a becomes sorted, or report that it is impossible.

Input
The first line contains one integer t (1≤t≤500) — the number of test cases.

Each test case consists of two lines. The first line contains two integers n and x (1≤n≤500, 0≤x≤500) — the number of elements in the sequence and the initial value of x.

The second line contains n integers a1, a2, …, an (0≤ai≤500).

The sum of values of n over all test cases in the input does not exceed 500.

Output
For each test case, print one integer — the minimum number of operations you have to perform to make a sorted, or ?1, if it is impossible.

Example

input

6
4 1
2 3 5 4
5 6
1 1 3 4 4
1 10
2
2 10
11 9
2 10
12 11
5 18
81 324 218 413 324

output

3
0
0
-1
1
3

题意

对于一个长度为 n 的数组,每次步骤可以将一个元素 a[i] 与 x 互换(前提是 ai > x),求至少需要换几次使得数列成为非递减序列。

分析

我们发现每次交换以后都只能将一个位置上的数变小,并且一旦交换,这个位置的数就不能再变了(因为不比 x 大了),所以可以推断出,如果连续下降序列大于 2 ,就不可能通过操作使他变成非递减的了。
对于一个位置 i ,若 a[i] < a[i+1] ,那这个点就必须要通过交换来变小,如果交换会使得 a[i - 1] > a[i] 了,那么要先交换前面的一系列点,使得交换过后仍是非递减数列。

代码
#include<bits/stdc++.h>
using namespace std;int t;
int n,x;
int a[507];
int f[507];int main()
{
    scanf("%d",&t);while(t--){
    int ans = 0;scanf("%d%d",&n,&x);for(int i=1;i<=n;i++) scanf("%d",&a[i]), f[i] = 0;int flag = 1;for(int i=1;i<n;i++){
    if(a[i] > a[i + 1]){
    if(f[i - 1] == 1) flag = 0;f[i] = 1;}}if(flag == 0){
    printf("-1\n");continue;}for(int i=1;i<n;i++){
    if(f[i] == 0) continue;int j = i;while(a[j - 1] > x && j - 1 > 0) j--;if(j == i && a[i] <= x){
    flag = 0;break;}for(int k=j;k<=i;k++){
    if(x == a[k]) continue;//注意这边如果相等的不用交换 swap(x, a[k]);ans++;}if(a[i] > a[i + 1]){
    flag = 0;break;}}if(flag == 1) printf("%d\n",ans);else printf("-1\n");}return 0;
}
  相关解决方案