1293: [SCOI2009]生日礼物
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 2680 Solved: 1470
[Submit][Status][Discuss]
Description
小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。 小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。
Input
第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的位置。
Output
应包含一行,为最短彩带长度。
Sample Input
6 3
1 5
2 1 7
3 1 3 8
Sample Output
3
HINT
Source
1 #include "bits/stdc++.h"
2 using namespace std;
3 typedef long long LL;
4 const int MAX=1e6+5;
5 int n,K,ans,now,cnt,a[MAX];
6 struct Node{
7 int x,y;
8 bool operator < (const Node &tt) const { return x<tt.x; }
9 }cad[MAX];
10 inline int read(){
11 int an=0,x=1;char c=getchar();
12 while (c<'0' || c>'9') {if (c=='-') x=-1;c=getchar();}
13 while (c>='0' && c<='9') {an=(an<<3)+(an<<1)+c-'0';c=getchar();}
14 return an*x;
15 }
16 void add(int x){if (!a[cad[x].y]) now++;a[cad[x].y]++;}
17 void del(int x){a[cad[x].y]--;if (!a[cad[x].y]) now--;}
18 int main(){
19 freopen ("present.in","r",stdin);freopen ("present.out","w",stdout);
20 int i,j,zt;
21 n=read();K=read();
22 for (i=1;i<=K;i++){
23 zt=read();
24 for (j=1;j<=zt;j++)
25 cad[++cnt].x=read(),cad[cnt].y=i;
26 }
27 sort(cad+1,cad+cnt+1);
28 add(1);int L=1,R=1;ans=1e9;
29 while (L<n){
30 while (now<K && R<n) add(++R);
31 if (now>=K) ans=min(ans,cad[R].x-cad[L].x);
32 del(L),++L;
33 }
34 printf("%d",ans);
35 return 0;
36