D. Sequence and Swaps(模拟+枚举) Educational Codeforces Round 99 (Rated for Div. 2)
程序员文章站
2022-06-04 18:38:14
...
原题链接: http://codeforces.com/contest/1455/problem/D
测试样例
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 n n的整数序列 n n n和一个整数 x x x,现在你可以进行操作为:选择序列中的下标 i ( 1 ≤ i ≤ n ) i(1\leq i \leq n) i(1≤i≤n),若 a i > x a_i>x ai>x,你可以交换 x x x和 a i a_i ai的值。你要进行这最少的操作次数使得这整数序列有序,若不可能,则输出 − 1 -1 −1。
解题思路: 我们想一下,如果我们要进行操作,那么必定是会将整数序列中的一个值给替换出来,而这个值我们必然可以模拟的,因为
n
≤
500
n\leq 500
n≤500。所以我们可以去模拟,并用模拟完成的数组排序与原数组进行比较,因为如果交换了那么必定小于原数组的值(因为每次交换是换掉比
x
x
x大的值。) 那么我们在比对过程中进行的操作次数即是排序数组小于原数组值的次数。而当排序数组大于原数组的值时,说明不可能。(因为每次交换是换掉比
x
x
x大的值。)故此题得解。
AC代码
/*
*blog:https://blog.csdn.net/hzf0701
*邮箱:aaa@qq.com
*注:文章若有任何问题请私信我或评论区留言,谢谢支持。
*/
#include<bits/stdc++.h>
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
using namespace std;
typedef long long ll;
const int maxn=1e5;//数组所开最大值
const int mod=1e9+7;//模
const int inf=0x3f3f3f3f;//无穷大
int t,n,x,a[510];
void solve(int *a){
//判断是否原数组就有序。
bool flag=true;
rep(i,0,n-2){
if(a[i]>a[i+1]){
flag=false;
break;
}
}
if(flag){
cout<<0<<endl;
return;
}
int ans=inf,cnt;
vector<int> b;
rep(i,0,n-1){
b.clear();
cnt=0;
rep(j,0,n){
if(i!=j){
b.push_back(a[j]);
}
}
sort(b.begin(),b.end());
rep(j,0,n-1){
if(b[j]>a[j]){
//由于只能替换比它大的,故若替换所处元素必定小于原值。
cnt=inf;
break;
}
else if(b[j]<a[j]){
cnt++;
}
//相等说明没有替换。
}
ans=min(ans,cnt);
}
if(ans==inf){
cout<<-1<<endl;
}
else{
cout<<ans<<endl;
}
}
int main(){
while(cin>>t){
while(t--){
cin>>n>>x;
rep(i,0,n-1){
cin>>a[i];
}
a[n]=x;
solve(a);
}
}
return 0;
}
上一篇: Python开发个人专属表情包网站
下一篇: 虚幻4实现自己移动的AI人物
推荐阅读
-
Educational Codeforces Round 97 (Rated for Div. 2) D. Minimal Height Tree
-
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
-
D. Sequence and Swaps(模拟+枚举) Educational Codeforces Round 99 (Rated for Div. 2)
-
Educational Codeforces Round 91 (Rated for Div. 2) D. Berserk And Fireball
-
Educational Codeforces Round 83 (Rated for Div. 2) D. Count the Arrays
-
Educational Codeforces Round 43 (Rated for Div. 2) D. Degree Set
-
Educational Codeforces Round 55 (Rated for Div. 2) D. Maximum Diameter Graph (构造图)
-
Educational Codeforces Round 49 (Rated for Div. 2)-D. Mouse Hunt
-
Educational Codeforces Round 39 (Rated for Div. 2) D. Timetable - dp分组背包
-
B. RPG Protagonist[Educational Codeforces Round 94 (Rated for Div. 2)]数学枚举