网站导航样式,金融投资理财网站建设,网站建设与管理软件,东莞娱乐场所最新通知文章目录 1. 题面2. 简单分析3. 代码解答4. TLE的2点可能 1. 题面
给定 N N N个区间 [ a i , b i ] [a_i,b_i] [ai,bi] 以及一个区间 [ s , t ] [s,t] [s,t]#xff0c;请你选择尽量少的区间#xff0c;将指定区间完全覆盖。
输出最少区间数#xff0c;如果无法完全… 文章目录 1. 题面2. 简单分析3. 代码解答4. TLE的2点可能 1. 题面
给定 N N N个区间 [ a i , b i ] [a_i,b_i] [ai,bi] 以及一个区间 [ s , t ] [s,t] [s,t]请你选择尽量少的区间将指定区间完全覆盖。
输出最少区间数如果无法完全覆盖则输出 −1。
输入格式
第一行包含两个整数 s 和 t表示给定区间的两个端点。
第二行包含整数 N表示给定区间数。
接下来 N 行每行包含两个整数 [ a i , b i ] [a_i,b_i] [ai,bi] 表示一个区间的两个端点。 输入样例
1 5
3
-1 3
2 4
3 5输出样例
22. 简单分析
这道题的贪心还是非常直观的。
将区间按从左到右的顺序排序每次选择能够覆盖给定区间起点的区间中右端点最远的区间。将起点更新为该区间的右端点。回到2进行循环直到右端点超过区间终点。
很简单的思路。但是实现的时候出了好几个bug所以记录一下。
3. 代码解答
#include iostream
#include algorithmusing namespace std;const int N 100010;struct Range {int l, r;bool operator (const Range rg)const {return l rg.l;}
}ranges[N];int main() {int n, a, b;cin a b n;for (int i 0; i n; i ) cin ranges[i].l ranges[i].r;sort(ranges, ranges n);int res 0;for (int i 0; i n; i ) {int j i, m -2e9; // m 为区间右端点最大值while (j n ranges[j].l a) {m max(m, ranges[j].r);j ;}if (m a) {break;}res ;a m;i j - 1;if (m b) {cout res;return 0;}}cout -1;return 0;
}import java.util.*;class Range implements ComparableRange {int l, r;public Range(int l, int r) {this.l l;this.r r;}public int compareTo(Range rg) {return Integer.compare(this.l, rg.l);}
}public class Main {public static void main(String[] args) {int N 100010;Range[] ranges new Range[N];Scanner sc new Scanner(System.in);int a sc.nextInt(), b sc.nextInt(), n sc.nextInt();for (int i 0; i n; i ) {int l sc.nextInt(), r sc.nextInt();ranges[i] new Range(l, r);}Arrays.sort(ranges, 0, n);int res 0;for (int i 0; i n; i ) {int j i, m -0x3f3f3f3f;while (j n ranges[j].l a) {m Math.max(ranges[j].r, m);j ;}if (m a) break;res ;a m;i j - 1;if (m b) {System.out.println(res);return;}}System.out.println(-1);}
}4. TLE的2点可能
将区间右端点的最大值设置为外部变量了。 以下面我的代码来说不能将m设置为for循环外部变量,如果设置为外部变量仍需要在循环内每次赋新值否则当所给区间不能覆盖中间某区域时while循环体不会执行那么 j ii i- 1就会陷入循环。手误将while循环中的 j 写为 i 了。同样的会发生 j 不更新问题。j ii i- 1就会陷入循环。
