「NOIP模拟赛」Erlang

观察,观察,观察......

Erlang

时间限制1s1\mathtt{s} 空间限制512MB512\mathtt{MB}

题目描述

小W新学会了一种编程语言Erlang。小W知道Erlang是一个面向并发的程序设计语言,于是就开始拿它写并发的程序了。他写了一个程序,包含一个主进程和 nn 个子进程,每个子进程都在不断和主进程通信。按照程序的设定,每次通信都是由子进程给主进程传输一个数。

但是小W的程序现在出现了些偏差,他发现主进程结束不了了。原本的剧本是主进程收到任意一个子进程给它传输一个 1-1 就结束,他发现现在变成了主进程收到的所有数里面存在两个数相同,主进程才能结束。

他为了让自己的程序快点结束,他研究了一下那些进程。他发现第 ii 个子进程将要给主进程传输 kik_i 个数,分别是 。他可以通过操作,控制主进程接受子进程传输的顺序。他每次可以选择一个还没传输完的所有的子进程 xx,然后让主进程和子进程 xx 通信一次,子进程 xx 会从它剩下的数中随机选一个传输给主进程。他想要知道在最优策略下,他最坏要通信多少次才能让子进程结束。

一句话题意:现在一共有 nn 个可重集 SiS_i,小W每次可以选择一个非空的集合,然后从里面随机抽取一个数,然后把这个数从集合中删掉。当存在两次抽取出来的数相等时结束。小W想要最小化最坏情况下的操作次数。

输入格式

第一行一个整数 nn

接下来 nn 行,每行第一个整数是 kik_i,后面跟 kik_i 个整数,表示 ai,ja_{i,j}

输出格式

输出一行表示最坏情况下的通信次数,若主进程不可能停下来,输出 1-1

样例输入

1
2
3
4
5
6
7
6
3 1 2 3
1 1
1 2
1 3
1 4
1 5

样例输出

1
2

样例解释

先选第一个集合,如果是 11 就选第 22 个集合,如果是 22 就选第 33 个集合,如果是 33 就选第 44 个集合。

数据规模与约定

Subtask #1 (10 pts):n1,ki105n \le 1, \sum k_i \le 10^5

Subtask #2 (20 pts):n5,ki10n \le 5, \sum k_i \le 10

Subtask #3 (30 pts):n,ki1000n, \sum k_i \le 1000

Subtask #4 (40 pts):

Solution

结论:

最优选取情况只可能是下面两种:

  1. 在一个集合中选取两个相同元素。
  2. 只在两个集合中选择元素,且从一个集合中选取,再从另一个集合中选取。

我们可以先处理出去出每个元素(值)的最小代价。其次,如果一个集合中的某个元素在别的集合中被取出的代价非常高,那么在最坏情况下,我们在这个集合中将这个元素取出。

那么就可以将枚举的集合中的元素按照代价大小排序,然后计算总代价即可。

Hint: 可能该元素的最小代价为当前枚举集合下,所以应处理出最小值和次小值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define re register int
#define rep(i,a,b) for(re i=a;i<=b;++i)
inline void Chkmin(int &a,int b) {a=min(a,b);}

int n, c[500005], Min[500005][2];
int ans=1e9;
vector<int> v[500005];

int main() {
scanf("%d", &n);
int a, k;
memset(Min, 0x3f, sizeof Min);
rep(i,1,n) {
scanf("%d", &k), c[i]=k;
rep(j,1,k) scanf("%d", &a), v[i].push_back(a);
sort(v[i].begin(),v[i].end());
c[i] = unique(v[i].begin(),v[i].end())-v[i].begin();
if(c[i]!=k) Chkmin(ans,c[i]+1);

for(int x:v[i]) {
if(Min[x][0]>c[i]) Min[x][1]=Min[x][0], Min[x][0]=c[i];
else if(c[i]<Min[x][1]) Min[x][1]=c[i];
}
}

rep(i,1,n) {
for(int &x:v[i]) x=Min[x][Min[x][0]==c[i]];
sort(v[i].begin(),v[i].end(),greater<int>());
for(unsigned z=0;z<v[i].size();++z) Chkmin(ans, v[i][z]+z+1);
}
printf("%d\n", ans<1e8?ans:-1);
return 0;
}