526互联

Largest Subsequence

发布时间 2024-01-05 15:08:43作者: yufan1102

image
image
image
image
image

操作：选取词性最大的子序列，向右循环一次

问你进行多少次这样的操作能使数组有序，如果不能就输出-1

思路：首先要知道的是一个词性最大的序列整个右移过后，数组的新词性最大的序列就是之前的词性最大序列去了最后一个字母.

找出词性最大的子序列
                int n;
		string s;
		cin>>n>>s;
		for(int i=0;i<n;i++){
			pos[s[i]-'a'].push_back(i);
		}
		vector<int>a;
		int j=-1;
		for(int i=25;i>=0;i--){
			if(pos[i].size()==0)continue;
			for(auto c:pos[i]){
				if(c>j){
				a.push_back(c);
				j=c;	
				}
			}
		}

然后我们想的是这个子序列应该是循环到第一个字母到最后了就可以了，次数可能是序列的长度-1

但其实举个例子zzzeca -> zzzec -> zzze -> zzz 它实际上只用了3次就变成了有序，所有我们不妨猜测一下这个次数应该是子序列的长度-最大字母的个数。

#include<bits/stdc++.h>
using namespace std;
vector<int>pos[25];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		for(int i=0;i<=25;i++){
			pos[i].clear(); 
		}
		int n;
		string s;
		cin>>n>>s;
		for(int i=0;i<n;i++){
			pos[s[i]-'a'].push_back(i);
		}
		vector<int>a;
		int j=-1;
		for(int i=25;i>=0;i--){
			if(pos[i].size()==0)continue;
			for(auto c:pos[i]){
				if(c>j){
				a.push_back(c);
				j=c;	
				}
			}
		}
		int cnt=0;
		for(int i=25;i>=0;i--){
			if(pos[i].size()!=0){
				cnt=pos[i].size();
				break;
			}
		}
		int m=a.size();
		for(int i=0;i<m/2;i++){
			int x=a[i];
			int y=a[m-i-1];
			swap(s[x],s[y]);
		}
		int f=0;
		for(int i=0;i<n-1;i++){
		if(s[i]>s[i+1]){
			f=1;
			break;
		}
	}
	f==1?cout<<-1<<"\n":cout<<a.size()-cnt<<"\n";
	}
	return 0;
}