[SCOI2009]生日礼物 题解
题目地址:洛谷:【P2564】[SCOI2009]生日礼物 – 洛谷、BZOJ:Problem 1293. — [SCOI2009]生日礼物
题目描述
小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。
小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。
题意简述
有K种颜色的珠子共N个,分别在一长段彩带的不同位置,可能存在多个珠子在同一位置的情况,求最短的子彩带使得彩带上具有所有K种颜色的珠子,长度定义为终止坐标-起始坐标。
输入输出格式
输入格式:
第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的位置。
输出格式:
输出应包含一行,为最短彩带长度。
输入输出样例
输入样例#1:
6 3 1 5 2 1 7 3 1 3 8
输出样例#1:
3
说明
【样例说明】
有多种方案可选,其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据, N≤10000;
对于80%的数据, N≤800000;
对于100%的数据,1≤N≤1000000,1≤K≤60,0≤Ti<231。
题解
本题可以用一个叫做“双指针”的算法解决。我们将珠子按照它们的坐标排序后,固定这个序列的左端(左指针),寻找一个最近的右端位置(右指针)使得左端到右端之间包含了所有颜色的珠子。由于有左右两个指针,我们把这种算法叫做双指针。具体而言,我们可以用一个cnt数组维护指针之间的区间内每种颜色珠子的数量,如果归0就对种类数-1,如果从0变为非0就对种类数+1。那么我们只需要让左指针左移时减去上一个位置的珠子,然后再寻找右指针的位置,这样维护一通,并且对每一对左右指针求长度更新答案即可。
排序采用STL排序,复杂度O(n \log n),根据上面的描述,双指针算法是O(n)的,因此总复杂度O(n \log n),可以通过本题。
双指针是常用的基础算法,常常能在CF题中见到它。
代码
// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <vector>
#include <utility>
typedef long long LL;
typedef std::pair<int, int> PII;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
register char c = fgc();
while(!isdigit(c)) {
if(c == '-') neg = -1;
c = fgc();
}
while(isdigit(c)) {
res = (res << 1) + (res << 3) + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 1000005;
int n, k, cnt[MAXN];
std::vector<PII> vec;
int main() {
n = readint(); k = readint();
for(int i = 1, ti, pos; i <= k; i++) {
ti = readint();
while(ti--) {
pos = readint();
vec.push_back(PII(pos, i));
}
}
std::sort(vec.begin(), vec.end());
int ans = 1e9, sum = 0;
int r = 0;
for(int l = 0; l < vec.size(); l++) {
while(r < vec.size() && sum < k) {
if(!cnt[vec[r].second]) sum++;
cnt[vec[r].second]++;
r++;
}
if(r >= vec.size() && sum < k) break;
ans = std::min(ans, vec[r - 1].first - vec[l].first);
cnt[vec[l].second]--;
if(!cnt[vec[l].second]) sum--;
}
printf("%d", ans);
return 0;
}