P2564 [SCOI2009] 生日礼物

P2564 [SCOI2009] 生日礼物

#include <bits/stdc++.h>
using namespace std;#define int long long
const int maxn = 1e6 + 10;
struct node{int pos,cate;
};
vector<node> v;
int n,k,cnt[maxn] = {0},type = 0;
bool cmp(const node &a ,const node &b){return a.pos < b.pos; 
}signed main(){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> k;for(int i = 1; i <= k; i++){//种类 int t;cin >> t;while(t--){int p;cin >> p;v.push_back({p,i});} }sort(v.begin(),v.end(),cmp);//for(int i = 0; i < n; i++)//cout << i <<" " << v[i].cate << " " <<v[i].pos << endl;int l = 0, r = 0,ans = 0x3f3f3f3f;while(r < n){if(!cnt[v[r].cate]) type++;cnt[v[r].cate]++;while(type == k){ans = min(ans,v[r].pos - v[l].pos);cnt[v[l].cate]--;if(!cnt[v[l].cate]) type--;l++;}r++;} cout << ans;return 0;
}