「BZOJ1293」[SCOI2009] 生日礼物
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
1 5
2 1 7
3 1 3 8
Sample Output
3
HINT
有多种方案可选，其中比较短的是1~5和5~8。后者长度为3最短。
「数据规模」
对于50%的数据， N≤10000；
对于80%的数据， N≤800000；
对于100%的数据，1≤N≤1000000，1≤K≤60，0≤彩珠位置<2^31。
题解
枚举起点找出每一种颜色在这个位置之后的第一个位置与这个位置距离的最大值，再找出每一个起点结果的最小值
可以用堆或者这个是叫做单调队列么。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define inf 0x7fffffff using namespace std; int n,k,cnt,ans=inf; int head[65]; int next[1000005],v[1000005],a[1000005]; inline int read() { char ch=getchar(); int f=1,x=0; while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();} return x*f; } bool cal(int x) { int mx=0; for(int i=1;i<=k;i++) { while(v[head[i]]>x) { if(!next[head[i]])return 0; head[i]=next[head[i]]; } if(v[head[i]]<=x)mx=max(mx,x-v[head[i]]); } ans=min(ans,mx); return 1; } int main() { n=read();k=read(); for(int i=1;i<=k;i++) { int x=read(); for(int j=1;j<=x;j++) { int y=read(); v[++cnt]=y; next[cnt]=head[i]; head[i]=cnt; a[cnt]=y; } } sort(a+1,a+cnt+1); for(int i=cnt;i>0;i--) { if(a[i]!=a[i+1]) if(!cal(a[i]))break; } printf("%d",ans); return 0; } |
计数器 9793226
OI 课件=>
OI 课件=>
Orz…你好，我想知道你的codeforce账号。我练习acm 1 年了。我想要变强，我想知道你的codeforce账号。你好 我叫newgate