题解 P2564 【[SCOI2009]生日礼物】

· · 题解

需要将所有彩珠的位置从小到大排序；

枚举一个位置x，需要快速知道每种彩珠≤x的位置，这个需要将每种彩珠出现的位置按从大到小的顺序存在链表中；

一个优化：因为从大到小枚举x，所以可以将每种彩珠位置所在的链表中位置>x的节点都删除

附上代码

#include <iostream>
using namespace std;
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <cstdlib>
const int N=1000005;
const int oo=2147483647;
typedef long long LL;
inline void get(int &x){char c=getchar();x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return ;
}
int n,k;
struct node{
    LL x;
    int id;
    bool operator < (const node& y) const{
        return x<y.x;
        }
    }p[N];
int len=0;
int a[N];
LL ans=0;
int maxm=0,minm=oo;
int main(){
    get(n);get(k);
    int i,j,x;
    for(i=1;i<=k;i++){
        int t;
        get(t);
        for(j=1;j<=t;j++){
            get(x);
            p[++len].x=x;
            p[len].id=i;
            maxm=max(x,maxm);
            minm=min(x,minm);
            }
        }
    sort(p+1,p+n+1);
    j=x=0; ans=maxm-minm;
    memset(a,0,sizeof(a));
    for(i=1;i<=n;i++){
        while(j<n&&x<k){
            j++;
            if(!a[p[j].id]) x++;
            a[p[j].id]++;
            }
            if(x<k) break;
            ans=min(ans,p[j].x-p[i].x);
            a[p[i].id]--;
            if(!a[p[i].id]) x--;
        }
    printf("%lld\n",ans);
    return 0;
}