题意
你有 个元素，种类未知，三种操作：
- 选取元素 ；
- 不选元素 ；
- 查询选取的元素中，出现最多的种类出现了多少次。
三种操作均可执行最多 次，你需要求出所有元素中出现最少的种类出现了多少次。
交互库非自适应。
思路
先尝试得到种类的数量。
可以先按顺序选取所有元素，如果最多的种类出现了两次，那么就把刚选的元素丢掉，保证每个种类只出现一次。
最后种类数即为选取的元素数，设为 。
然后思考求答案，不妨假设答案为 ，那么显然，每个种类都至少有 个元素。
但是不满足每个种类都至少有 个元素，也就是说，令每个种类选取 个元素，实际选取的元素数小于 。
这样转化为判定问题，满足可二分性。
实现
但是卡常。
首先你发现向下二分的时候，没选的就用不上了。
同理向上二分的时候，选了的就一直选。
然后二分上界设为 ，这样就几乎可以通过此题。
但是良心出题人枚举了你所有可能的二分实现并构造了数据卡你一分
需要在二分的时候随机加一来扰动避免极端情况。
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
39
40
41
42
43
44
45
| #include "insects.h"
#include<random>
#include<chrono>
std::mt19937 rnd(std::chrono::steady_clock().now().time_since_epoch().count());
namespace {int a[2010],cnt,col;}
int min_cardinality(int n){
for(int i=0;i<n;++i){
move_inside(i);
if(press_button()<2){
++cnt;
a[i]=-1;
}else move_outside(i);
}
col=cnt;
int l=1,r=n/cnt,ans;
for(;l<=r;){
int t=(l+r)>>1;
if((l+r)&1) t+=rnd()&1;
for(int i=0;i<n;++i)
if(a[i]==0){
move_inside(i);
if(press_button()<=t){
a[i]=1;
if(++cnt==t*col) break;
}else move_outside(i);
}
if(cnt==t*col){
for(int i=0;i<n;++i)
if(a[i]==1) a[i]=-1;
ans=t;
l=t+1;
}else{
for(int i=0;i<n;++i){
if(a[i]==0) a[i]=-1;
if(a[i]==1){
--cnt;
move_outside(i);
a[i]=0;
}
}
r=t-1;
}
}
return(ans);
}
|