按区间长度降序排序维护区间指针 [l, r], 第 l ~ r 条线段 表示当前区间可以满足条件那么 r 后移一定不是更优的因此 l 前移, 使得 r 后移过程中取最小值更新 answer
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cmath>
- #include <cstring>
- #include <string>
- using namespace std;
- #define LL long long
- #define gc getchar()
- inline int read() {int x = 0; char c = gc; while(c <'0' || c> '9') c = gc;
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}
- inline LL read_LL() {LL x = 0; char c = gc; while(c <'0' || c> '9') c = gc;
- while(c>= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}
- #undef gc
- const int N = 1e6 + 10;
- struct Node {int l, r, len;} G[N>> 1];
- int A[N];
- int Max[N <<2], W[N << 2], F[N << 2];
- int n, m;
- inline bool Cmp(Node a, Node b) {return a.len> b.len;}
- #define lson jd <<1
- #define rson jd << 1 | 1
- void Push_down(int jd) {
- F[lson] += F[jd], F[rson] += F[jd];
- Max[lson] += F[jd], Max[rson] += F[jd];
- F[jd] = 0;
- }
- void Sec_G(int l, int r, int jd, int x, int y, int num) {
- if(x <= l && r <= y) {
- Max[jd] += num;
- F[jd] += num;
- return ;
- }
- if(F[jd]) Push_down(jd);
- int mid = (l + r)>> 1;
- if(x <= mid) Sec_G(l, mid, lson, x, y, num);
- if(y> mid ) Sec_G(mid + 1, r, rson, x, y, num);
- Max[jd] = max(Max[lson], Max[rson]);
- }
- bool use[N];
- int main() {
- n = read(), m = read();
- int tot = 0;
- for(int i = 1; i <= n; i ++) {
- G[i].l = read(), G[i].r = read(), G[i].len = G[i].r - G[i].l; A[++ tot] = G[i].l, A[++ tot] = G[i].r;
- }
- sort(G + 1, G + n + 1, Cmp);
- sort(A + 1, A + tot + 1);
- for(int i = 1; i <= n; i ++) {
- G[i].l = lower_bound(A + 1, A + tot + 1, G[i].l) - A;
- G[i].r = lower_bound(A + 1, A + tot + 1, G[i].r) - A;
- }
- int R = 1, Answer = (int)1e9 + 9;
- for(int i = 1; i <= n; i ++) {
- if(R == n) break;
- if(use[i] == 0) {
- Sec_G(1, tot, 1, G[i].l, G[i].r, 1);
- use[i] = 1;
- }
- while(Max[1] <m && R < n) {
- R ++;
- Sec_G(1, tot, 1, G[R].l, G[R].r, 1);
- use[R] = 1;
- if(Max[1]>= m) {
- Answer = min(Answer, G[i].len - G[R].len);
- break;
- }
- }
- if(use[i]) {
- Sec_G(1, tot, 1, G[i].l, G[i].r, -1);
- use[i] = 0;
- }
- }
- if(Answer == (int)1e9 + 9) cout << "-1";
- else cout << Answer;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2751144.html