題意：給你n個k種顏色的點，每個點都有坐標和顏色兩個屬性，選出一個長度盡量短的區間，使得每種顏色的點都在區間內出現。

?

數據范圍：

對于50%的數據， N≤10000；

對于80%的數據， N≤800000；

對于100%的數據，1≤N≤1000000，1≤K≤60，0≤珠子位置<2^{31}。

--------------------------------------------------我是分割線-------------------------------------------------------

題解：單調性尺取法的經典應用。先將點按照坐標排序，用兩個變量l和r來枚舉區間，如果l到r的區間不滿足要求，r++，如果l到r的區間滿足要求，記錄答案，l++。

排序時間復雜度O（NlogN），尺取時間復雜度O（N），總時間復雜度O（NlogN）。

#include<bits/stdc++.h>#define ll long long #define mp make_pair #define rep(i, a, b) for(int i = (a); i <= (b); i++) #define per(i, a, b) for(int i = (a); i >= (b); i--)using namespace std;typedef pair<int, int> pii; typedef double db; const int N = 1e6 + 50; struct node { int x, id; } a[N]; int n, k, h, vis[N], q[N], u, ans = 1e9, cnt; 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<<3)+(x<<1)+(ch^48); ch = getchar();}return x*f; } bool mycmp(node a, node b){ return a.x < b.x; } void insert(int x) { if(vis[x] == 0) cnt++; vis[x]++; } void remove(int x) { if(vis[x] == 1) cnt--; vis[x]--; } void init(){n = read(); k = read();rep(i, 1, k){int t = read();rep(j, 1, t) a[++h].x = read(), a[h].id = i;}sort(a+1, a+n+1, mycmp); } void work(){int l = 1, r = 1;while(r <= n){insert(a[r].id);while(true) {remove(a[l].id); if(cnt == k) l++;else { insert(a[l].id); break;}}if(cnt == k) ans = min(ans, a[r].x - a[l].x);r++;}printf("%d\n", ans); } int main(){init();work();return 0; } View Code

?

轉載于:https://www.cnblogs.com/smilke/p/11580240.html

總結

以上是生活随笔為你收集整理的[SCOI2009]生日礼物 单调性尺取法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。