P14971 『GTOI - 2B』DDoS
题目描述
现在有n nn个人提交代码给洛谷，其中第i ii个人提交代码的时间是第l i l_ili秒至第r i r_iri秒（包括第l i , r i l_i,r_ili,ri秒）。
小 H 可以进行若干次操作，每次操作选择两个正整数x , y x,yx,y满足x ≤ y x\le yx≤y，用y − x + 1 y-x+1y−x+1的代价在区间[ x , y ] [x,y][x,y]所对应的时间，即第x xx秒到第y yy秒内（包括第x , y x,yx,y秒）向洛谷发起 DDoS 攻击。小 H 可使用的总代价为m mm。
小 H 希望所有的n nn个人在提交代码时都全程受到 DDoS 攻击。
我们认为第i ii个人提交代码时全程受到 DDoS 攻击，当且仅当对于∀ j ∈ [ l i , r i ] \forall j\in[l_i,r_i]∀j∈[li,ri]，第j jj秒有 DDoS 攻击。
由于小 H 讨厌不连续的攻击，所以他问你，他至少要进行几次操作，才能使得这n nn个人提交代码时都全程受到 DDoS 攻击。
如果无论如何都不能使得这n nn个人提交代码时都全程受到 DDoS 攻击，输出− 1 -1−1。
输入格式
第一行，两个正整数n , m n,mn,m。
接下来n nn行，每行两个正整数l i , r i l_i,r_ili,ri。
输出格式
一个整数，表示最小的操作次数，无解输出-1 \text{-1}-1。
输入输出样例 #1
输入 #1
5 12 2 4 11 12 6 8 1 3 10 13输出 #1
2输入输出样例 #2
输入 #2
5 12 1 3 6 9 4 5 2 4 10 12输出 #2
1输入输出样例 #3
输入 #3
2 14 1 10 2 15输出 #3
-1说明/提示
【数据范围】
本题采用捆绑测试。
对于100 % 100\%100%的数据，保证1 ≤ n ≤ 10 6 , 1 ≤ m , l i , r i ≤ 10 9 1 \le n \le 10^6,1 \le m,l_i,r_i \le 10^91≤n≤106,1≤m,li,ri≤109。
| Subtask \text{Subtask}Subtask | n nn | m , l i , r i m,l_i,r_im,li,ri | 分值 |
|---|---|---|---|
| 1 11 | ≤ 10 \le10≤10 | ≤ 10 6 \le10^6≤106 | 20 2020 |
| 2 22 | ≤ 10 5 \le10^5≤105 | ≤ 10 6 \le10^6≤106 | 30 3030 |
| 3 33 | ≤ 10 6 \le10^6≤106 | ≤ 10 9 \le10^9≤109 | 50 5050 |
思路
直接暴力。
代码见下
#include<bits/stdc++.h>usingnamespacestd;longlongn,m,dl=1,db=0,op=0,b[1000006],de=0,fk=0;structone{longlongl,r;}a[1000006];boolcmp(one a1,one b1){returna1.l<b1.l;}map<longlong,longlong>mp;intmain(){cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i].l>>a[i].r;}sort(a+1,a+n+1,cmp);for(inti=1;i<=n;i++){if(db<=a[i].l-2){op+=(db-dl+1);if(i!=1)b[++de]=(a[i].l-db-1);dl=a[i].l;db=a[i].r;fk++;}else{db=max(db,a[i].r);}}op+=(db-dl+1);//fk++;if(m<=op-1){cout<<-1<<endl;}else{sort(b+1,b+de+1);for(inti=1;i<=de;i++){if(op+b[i]<=m){op+=b[i];fk--;}// else{// break;// }}cout<<fk<<endl;}return0;}
