题解
显然,最多抽2个集合
如果一直抽一个,前提是该集合有重复的,答案是不同元素的个数+1
如果抽两个,那么最坏情况下,在一个集合中抽到某一个数的次数是这个集合不同元素的个数(因为抽不到重复的)
枚举其中一个集合 \(S\) ,对于每一种元素,令 \(f[i]\) 表示第 \(i\) 个元素在其他集合中最少要多少次抽到,将 \(f\) 数组从大到小排序,设 \(i\) 的排名为 \(rk_i\),那么最坏情况下取 \(i\) 这个元素的条件是 在 \(S\) 中抽了 \(rk_i\) 次(如果超过 \(rk_i\) ,那么之前一定抽到了比 \(f[i]\) 更小的)
因此,在所有情况下求最小值就是答案
复杂度 \(O(能过)\)
#include#define REP(i,a,b) for(int i(a);i<=(b);++i)using namespace std;template 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 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.readconst int n=read(),N=5e5+5;vector 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