欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #591 (Div. 2)D. Sequence Sorting(思路)

程序员文章站 2022-06-18 11:26:55
...

题目链接:

https://codeforces.com/problemset/problem/1223/D

题面:

Codeforces Round #591 (Div. 2)D. Sequence Sorting(思路)

题意:

一次操作可以把一种数字(不一定是只有一个)移动到最左边或最右边,问最少经过几次操作可以使序列变成不下降序列。
ps:没初始化wawa了,数组开小了rere,我sb了orzorz。
Codeforces Round #591 (Div. 2)D. Sequence Sorting(思路)

思路:

考虑不需要移动的(也就是本身连续不减)数,这里用邻接表的形式存某种数的出现坐标,对数据去重,然后用sumsum表示当前需要移动的数数量,通过当前数出现的最后一个位置和下一个数出现的第一个位置从而判断当前数是否是不需要移动的,然后累加取最大值,最后用总的数的种类减去不需要移动的种类就是答案。

参考代码:

/* CF was purple years ago!
 * Thanks cf-tool!
 * Author: nuoyanli
 * Time: 2019-12-08 12:59:09
 **/

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 3e5 + 10;
ll n,t,sum,a[N],b[N];
vector<int>mmp[N];
ll solve() {
	sort(a+1,a+n+1);
	int num=unique(a+1,a+n+1)-a-1;
	/*	for(int i=1;i<=num;i++){
			cout<<a[i]<<" ";
		}
		cout<<endl;
	*/
	ll ans=1;
	sum=1;
	for(int i=1; i<num; i++) {
		int x=a[i],y=a[i+1];
		if(mmp[x].back()>mmp[y][0]) {
			sum=1;
		} else {
			sum+=1;
		}
		ans=max(ans,sum);
	}
	return num-ans;
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>t;
	while(t--) {
		cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>a[i];
			b[i]=a[i];
			mmp[a[i]].push_back(i);
		}
		cout<<solve()<<endl;
		for(int i=1; i<=n; i++) {
			mmp[b[i]].clear() ;
		}
	}
	return 0;
}
相关标签: 思路