[NOI.AC#40]Erlang

题解

显然，最多抽2个集合

如果一直抽一个，前提是该集合有重复的，答案是不同元素的个数+1

如果抽两个，那么最坏情况下，在一个集合中抽到某一个数的次数是这个集合不同元素的个数（因为抽不到重复的）

枚举其中一个集合 \(S\) ，对于每一种元素，令 \(f[i]\) 表示第 \(i\) 个元素在其他集合中最少要多少次抽到，将 \(f\) 数组从大到小排序，设 \(i\) 的排名为 \(rk_i\)，那么最坏情况下取 \(i\) 这个元素的条件是在 \(S\) 中抽了 \(rk_i\) 次（如果超过 \(rk_i\) ，那么之前一定抽到了比 \(f[i]\) 更小的）

因此，在所有情况下求最小值就是答案

复杂度 \(O(能过)\)

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i(a);i<=(b);++i)

using namespace std;

template<typename T,typename U>inline char smin(T&x,const U&y){return x>y?x=y,1:0;}

namespace IOManager{

	const unsigned int iSize(131072);

	char buf[iSize],*iT=buf+iSize,*iS=iT-1;

	struct FastIO{

		inline char gc(){

			if(++iS==iT)fread(iS=buf,1,iSize,stdin);return *iS;

		}

		template<typename T>

			inline void read(T&w){register char c,p=0;

				while(isspace(c=gc()));if(c=='-')p=1,c=gc();w=c^48u;

				while(isdigit(c=gc()))w=w*10+(c^48u);if(p)w=-w;

			}

		inline int read(){register int x;return read(x),x;}

	};

}IOManager::FastIO io;

#define read io.read

const int n=read(),N=5e5+5;

vector<int>g[N];

int cnt[N],fi[N],se[N],a[N];

int main(){

	int ans=1e9;

	memset(fi,0x3f,sizeof fi);

	REP(i,1,n){

		int k=read(),s;

		g[i].resize(k);

		for(int&x:g[i])x=read();

		sort(g[i].begin(),g[i].end());

		g[i].resize(s=unique(g[i].begin(),g[i].end())-g[i].begin());

		if(s<k)smin(ans,s+1);

		for(int x:g[i]){

			if(s<fi[x])se[x]=fi[x],fi[x]=s;

			else if(s<se[x])se[x]=s;

		}

	}

	REP(i,1,n){

		const int s=g[i].size();int k=0;

		for(int x:g[i])a[++k]=s==fi[x]?se[x]:fi[x];

		sort(a+1,a+1+k,greater<int>());

		REP(j,1,k)smin(ans,j+a[j]);

	}

	cout<<(ans==1e9?-1:ans);

	return 0;

}

巴特西

[NOI.AC#40]Erlang

题解

最新文章

热门文章