怎么去找做网站的,网站设计与开发培训,动漫制作专业介绍及就业方向,国际购物网站题意#xff1a;给你n个k种颜色的点#xff0c;每个点都有坐标和颜色两个属性#xff0c;选出一个长度尽量短的区间#xff0c;使得每种颜色的点都在区间内出现。 数据范围#xff1a; 对于50%的数据#xff0c; N≤10000#xff1b; 对于80%的数据#xff0c; N≤8000… 题意给你n个k种颜色的点每个点都有坐标和颜色两个属性选出一个长度尽量短的区间使得每种颜色的点都在区间内出现。 数据范围 对于50%的数据 N≤10000 对于80%的数据 N≤800000 对于100%的数据1≤N≤10000001≤K≤600≤珠子位置2^{31}。 --------------------------------------------------我是分割线------------------------------------------------------- 题解单调性尺取法的经典应用。先将点按照坐标排序用两个变量l和r来枚举区间如果l到r的区间不满足要求r如果l到r的区间满足要求记录答案l。 排序时间复杂度ONlogN尺取时间复杂度ON总时间复杂度ONlogN。 #includebits/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 pairint, 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 (x3)(x1)(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(a1, an1, 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
