bzoj 1112: [POI2008]砖块Klo set

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1112


2019-3-2回来更新

发现我当时这个思想就是对顶堆,我还一直以为对顶堆多神奇…


STL大法好!!

 

最开始查了查题解,觉得好麻烦啊不想照着写…所以就自己搞了搞

550人AC 排在rank35 还算不错…

题意:把连续k个数每次+1或-1,用最少的操作次数变为同一个数

有一个显而易见结论:一定把这连续k个都变为这k个数的中位数是最优的

所以我们要实现的是:快速找到[中位数],求出所有大于/小于[中位数]的数的和,并支持删除/插入一个数

看起来就像平衡树

但是不想打怎么办?  用set!


set里的元素不可重,所以我们用pair,first存值,second存下标

我们用两个set来分别维护连续k个数的前一半和后一半(1 ~ k/2)  (k/2+1 ~ k)

选中的连续k个数不断往后移,从1 ~ k到n-k+1 ~ n

因为set是有序的,所以第二个set的第一个数(也就是begin)就是我们要的中位数

中位数知道了,[和]我们可以insert的时候一边算出来,那么对于目前的序列的答案就知道了

插入/删除操作就直接通过set非常妙妙的erase就可以了,可以直接erase一个值/迭代器

所以插入/删除非常简单的就可以实现了


为了保证第一个set的元素全都小于等于第二个set里的,每次区间往后移了之后比较下s1.end()和s2.begin(),如果第一个大于第二个,我们就需要交换这两个元素

交换的过程和插入/删除非常的相似


代码:

数据生成器:

 

发表评论