题意
有 \(n\) 个二元组 \((a_i,b_i),1\leq a_i\leq k\), 将他们按 \(b\) 的升序排列, 求区间 \([l,r]\) 满足:
- \(1\leq l\leq r\leq n\).
- \(\bigcup_{
- i=l
- }^ra_i=\{
- 1,2,\cdots,k\
- }\).
要求最小化 \(b_r-b_l\).
\(n\leq 10^6,k\leq 60,b_i\leq 2^{31}\).
分析
典型的尺取法, 维护每一类出现的次数以及出现的类数, 尺取一下就行
- #include<cstdio>
- #include<algorithm>
- #include<queue>
- #define pii pair<int,int>
- using namespace std;
- const int N=1e6+6,K=65;
- int n,k,l,r,ans=0x3f3f3f3f;
- pii a[N];
- int times[K],tot;
- void movel(){
- times[a[l].second]--;
- if(!times[a[l].second])tot--;
- ++l;
- }
- void mover(){
- while(r<n&&tot<k){
- ++r;
- if(!times[a[r].second])++tot;
- times[a[r].second]++;
- }
- }
- int main(){
- scanf("%d%d",&n,&k);
- for(int i=1,cnt;i<=k;i++){
- scanf("%d",&cnt);
- for(int j=1,x;j<=cnt;j++)scanf("%d",&x),a[++l]=make_pair(x,i);
- }
- sort(a+1,a+n+1);
- l=1,r=0;
- do{
- mover();
- ans=min(ans,a[r].first-a[l].first);
- movel();
- }while(r<n);
- printf("%d",ans);
- return 0;
- }
[SCOI2009] 生日礼物
来源: http://www.bubuko.com/infodetail-3098895.html