AcWing907. 区间覆盖

2024-09-06 19:52
文章标签 覆盖 区间 acwing907

本文主要是介绍AcWing907. 区间覆盖,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

参考的视频讲解:↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
【贪心算法08-区间问题03-区间覆盖】
每次贪心就是选择左端点里面<起始端点里面右边界最大的,这样就是保证了最少区间个数!
然后每次迭代都会更新一次起始端点st,反复运用本算法。
一定要仔细看视频讲解!!!

#include<iostream>
#include<algorithm>
#define N 100010
#define INF 2e9
using namespace std;
int n ;
struct Range{int l, r;bool operator<(const Range& r1){return l < r1.l;}
}range[N];
int main(){int st , ed;cin >> st >> ed;cin >> n;for(int i = 0 ; i < n ; ++ i){int l , r ;cin >> l >> r;range[i] = {l ,r};} sort(range,range + n);int res = 0 ;bool success = false;for(int i = 0 ; i < n ; ++ i){int j = i ,r = -2e9;while(j < n && range[j].l <= st){r = max(r , range[j].r);++ j;}if(r < st){res = -1;//如果挑出来的最大右端点小于起始端点,那么无解,返回-1break;}++res;if(r >= ed){//如果右边界已经可以超过末尾端点ed,那么求解完毕,返回ressuccess = true;break;}st = r;i = j - 1;}if (!success) res = -1;printf("%d\n", res);
}

这篇关于AcWing907. 区间覆盖的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1142970

相关文章

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

最大流=最小割=最小点权覆盖集=sum-最大点权独立集

二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上,把每个点赋予一个非负的权值,这两个问题就转化为:二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点,使这些点覆盖所有的边,并且选出来的点的权值尽可能小。 建模:     原二分图中的边(u,v)替换为容量为INF的有向边(u,v),设立源点s和汇点t

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

POJ3041 最小顶点覆盖

N*N的矩阵,有些格子有物体,每次消除一行或一列,最少要几次消灭完。 行i - >列j 连边,表示(i,j)处有物体,即 边表示 物体。 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;impo

Minimal coverage -uva 覆盖线段,贪心

一道经典的贪心问题,具体方法就是将(an,bn)区间,按照an从小到大的顺序进行排序,之后从0开始, 取最大的有效区间,这里用到了结构体的快排,否则可能会超时. #include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 100000 + 10#define BOTTOM -50000 - 10str

【uva】11536-Smallest Sub-Array(区间移动问题)

一个区间移动的问题,1A了,感觉没什么好说的。。 13975926 11536 Smallest Sub-Array Accepted C++ 0.809 2014-08-01 11:00:20 #include<cstdio>#include<cstring>#include<iostream>using namespace std;#define INF 1 << 30

【hdu】Just a Hook(线段树区间修改)

线段树模板题,练的是懒惰标记。 懒惰标记,就是更新一段区间的时候,如果小区间被包含在了所需要更新的区间里面,那么直接对代表这个区间的数组元素赋值,之后做一个标记(表示这个区间的子区间都需要更新)但是不继续递归(这样可以节省很多的时候)。 116571152014-09-15 14:17:26Accepted1698796MS2380K1750 BG++KinderRiven #

【hdu】I Hate It(线段树,结点修改求区间最大值)

线段树的模板题,还是二分递归。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>#incl