题解 CF982D Shark

输入一串数,要求你找到一个满足以下条件的 \(k\)

  1. 所有小于 \(k\) 的数组成的连续子段长度要相等。
  2. 满足 \(1\) 的情况下段尽可能多。
  3. 满足前两条的情况下 \(k\) 尽可能小。

遇到这样限制很多的题目,一般考虑排个序去掉一个再考虑剩下的,所以直接排个序然后依次插入就保证满足 \(1\) 了。

那么只需要考虑怎么处理子段就行了。这题没有对一段里面数相对位置的要求,所以看成集合,用并查集即可。合并的时候顺便记录一下每个集合的大小,以及最大的,如果集合大小等于最大的的数量就是集合的数量就可以更新答案了。

代码其实很短啊,为什么其它题解看上去那么长。

// eq 是大小和最大的相等的段的数量,ml 是最大的大小,num 是集合数
void add(int x) {
	flag[x] = 1;
	flag[x-1] && (num --, eq -= size[find(x-1)] == ml, merge(x, x-1)), 
	flag[x+1] && (num --, eq -= size[find(x+1)] == ml, merge(x, x+1));
	num ++;
	int t = size[find(x)];
	if(ml < t) eq = 1, ml = t;
	else if(ml == t) eq ++;
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
	std::sort(a+1, a+1+n);
	for(int i = 1; i <= n; i++) fa[i] = i, size[i] = 1;
	for(int i = 1; i <= n; i++) {
		add(a[i].id);
		if(num == eq && (num > ann || (num == ann && ank > a[i].v+1))) 
			ank = a[i].v+1, ann = num;
	}
	printf("%d", ank);
}

题解 CF982D Shark

上一篇:基于mui.popover的支持多选的弹出列表组件改造以及mui.prompt添加自定义内容


下一篇:Mybatis和Mybatis-Plus时间范围查询