F1. Flying Sort (Easy Version)
题意
给出n个不重复的数 要求进行以下两种操作使得数组升序
1 将某位置的数移动到队列最前方
2 将某位置的数移动到队列最后方
问最小操作次数
题解
由于n个数互不相同离散化之后题目变为cf 606C
离散化技巧见代码
再贪心找最长连续上升子序列 设长为len
注意不是单纯的最长上升子序列是 最长的连续上升子序列(非子串)
连续的意思为这个上升子序列里相邻元素是连续的即差为1
答案为n-len
/*
cf 606C 题意
一个无限长的铁路有一个载着n辆车的火车，每一辆车的编号从1到n。每一辆车的编号都是不同的。他们的顺序是无序的。
David Blaine想要将这些车按照他们的编号从小到大排序，他可以做两种操作。第一种，他可以将一辆车从任意位置移动到所有车的第一位。第二种，他可以将一辆车从任意位置移动到所有车的最后一位。
不过他很懒，所以他想知道将这些车排好序最少做几次操作就可以。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
# define endl '\n'
# define Turnoff std::ios::sync_with_stdio(false)
const int Max=2e5+5;
const int Mod=998244353;
int arr[Max],len[Max];
vector<int>data;
inline int getid(int x){return lower_bound(data.begin(),data.end(),x)-data.begin()+1;}
int main() {
Turnoff;
int t;cin>>t;
while(t--){
int n;cin>>n;
data.clear();
int maxn=0;
for(int i=1;i<=n;i++){
cin>>arr[i];len[i]=0;
data.push_back(arr[i]);
}
sort(data.begin(),data.end());
for(int i=1;i<=n;i++){
int pos=getid(arr[i]);
len[pos]=len[pos-1]+1;
if(len[pos]>maxn)maxn=len[pos];
}
cout<<n-maxn<<endl;
}
}
|