OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【SCOI2009】生日礼物

【题目描述】

小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。

小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。

【输入】

第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的位置。

【输出】

包含一行,为最短彩带长度。

【输入样例】

6 3

1 5

2 1 7

3 1 3 8

【输出样例】

3

【数据范围】

对于50%的数据, N≤10000;

对于80%的数据, N≤800000;

对于100%的数据,1≤N≤1000000,1≤K≤60,0≤Ti<2^31。

【题解】

对于一个最优解,一定是左右两端都是彩珠。我们先将所有颜色的第一个彩珠加入一个堆中(关键字为编号的小根堆),得到一个答案,等同于枚举一个序列。以后每次删除掉序列最左端的彩珠,即删除堆顶,再将改颜色右边相邻的第一个彩珠加入堆中,不断更新答案,知道某种颜色的彩珠已经使用到最右端了,也就没有更优的答案了。

由于是小根堆,序列中最左端下标直接取对顶就好,但是最右端下标需要另外维护。再写一个数据结构是不大可能了,我们就使用一个变量来记录,每次和新入堆的比较,取最大值即可。这样做是正确的,因为删除只针对堆顶,而堆顶是下标最小值,所以不会因为删除操作更新最大值。

【代码】

STL怨念……

http://paste.ubuntu.com/8123473/

评论

© OI技术宅 | Powered by LOFTER