题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1293
题意：坐标轴上有 n 个点，点有颜色，求最短的包含所有颜色点的区间。
单调队列... 有点类似莫队的感觉...
|
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 57 58 59 60 61 62 63 64 65 66 67 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1000010 #define K 65 #define ll long long using namespace std; char xB[1<<15],*xS=xB,*xT=xB; #define getchar() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) inline int read() { int x=0,f=1;char ch=getchar(); 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; } struct zgz { int x,c; }a[N]; bool cmp(zgz a,zgz b) {return a.x<b.x;} int n,k,top,ans,tot; int q[N],hd,tl; int buc[K]; void get_in(int x) { q[++tl]=x; buc[a[x].c]++; if(buc[a[x].c]==1)tot++; } void push_out() { buc[a[q[hd]].c]--; if(buc[a[q[hd]].c]==0)tot--; hd++; } int main() { n=read(),k=read(); for(int i=1;i<=k;i++) { int tmp=read(); for(int j=1;j<=tmp;j++) { int tp=read(); a[++top].x=tp,a[top].c=i; } } ans=2000000000; sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) { get_in(i); while(tot==k) { ans=min(ans,a[q[tl]].x-a[q[hd]].x); push_out(); } } printf("%d\n",ans); } |
Comments | NOTHING