关于容器stl中multiset使用有感

此题是stl容器使用的高度集合

直接贪心遍历就行了，但是代码有点难写
因为要用到很多容器和stl的方法 
注意multiset和set的区别，前者不会去重 
vetcor里面是push_back
multiset里面是insert

对于multiset来说，*set.rbegin()就是获取到最后一个   是一个反向迭代器 
                  set.end()就是最后一个数字后面一位的迭代器
                set.erase() 里面只能填迭代器，所以不能填set.rbegin(),只能填--set.end()

题解代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#define ll long long
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
typedef pair<int,int> PII;
const ll inf=0x3f3f3f3f;
const int N=200010;
double p,q;
ll t,n,x,m,y,k;
ll a[N];
string s;
int cnt[23];
PII e[110];
//unordered_map<int,int> mp;

//直接贪心遍历就行了，但是代码有点难写
//因为要用到很多容器和stl的方法 
//注意multiset和set的区别，前者不会去重 
//vetcor里面是push_back
//multiset里面是insert
//
//对于multiset来说，*set.rbegin()就是获取到最后一个   是一个反向迭代器 
//                  set.end()就是最后一个数字后面一位的迭代器
//                set.erase() 里面只能填迭代器，所以不能填set.rbegin(),只能填--set.end() 
void solve(){
	cin>>n>>k;
	vector<int> out[k+1];
	multiset<int> ans[n+1];
	
	for(int i=1;i<=k;i++){
		out[i].push_back(0);
	}
	
	for(int i=1;i<=n;i++){
		cin>>a[i];
		out[a[i]].push_back(i);
	}
	for(int i=1;i<=k;i++)out[i].push_back(n+1);
	
	for(int i=1;i<=k;i++){
		for(int j=1;j<out[i].size();j++){
			ans[i].insert(out[i][j]-out[i][j-1]-1);
		}
	}
	
	for(int i=1;i<=k;i++){
		ll t=*ans[i].rbegin(); 
		ans[i].erase(--ans[i].end());
		ans[i].insert(t/2);
//		cout<<*ans[i].rbegin()<<' '<<*ans[i].end()<<'\n';
	}
	
	int maxx=n;
	for(int i=1;i<=k;i++){
		maxx=min(maxx,*ans[i].rbegin());
	}
	cout<<maxx<<'\n';
	
	
	
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
 
	cin>>t;
	while(t--){
		solve();
	}
	
}