NC20565（[SCOI2009]生日礼物 ）

感受


思路

复杂度：O(n^2)
for(l:1~n)
    for(r:l~n)
        if(区间[l,r]存在k种珍珠) ans = min(asn, r.pos - l.pos);

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1000000 + 10;
struct node{
    int id;
    ll pos;
    bool operator < (const node &c)const{
        return pos < c.pos;
    }
}b[maxn];
int n, k, tot;
int cnt[100];
ll ans;
void solve(){
    int num = 0;
    int l = 1, r = 0;
    while(r < tot){
        while(num != k && r < tot){
            r++;
            if(!cnt[b[r].id]){
                num++;
            }
            cnt[b[r].id]++;
        }
        while(num == k && l <= r){
            ans = min(ans, b[r].pos - b[l].pos);
            cnt[b[l].id]--;
            if(!cnt[b[l].id]) num--;
            l++;
        }
    }///[ , ]
}
void print(){
    for(int i = 1; i <= tot; i++){
        printf("(%d, %lld)\n", b[i].id, b[i].pos);
    }
}
int main(){
    scanf("%d%d", &n, &k);
    int num; ll pos;
    for(int i = 1; i <= k; i++){
        scanf("%d", &num);
        while(num--){
            scanf("%lld", &pos);
            tot++; b[tot].id = i; b[tot].pos = pos;
        }
    }
    sort(b + 1, b + tot + 1);
    ans = 1e10;
    solve();
    printf("%lld\n", ans);
    return 0;
}