贪心:区间问题
admin
2024-03-20 07:33:50
0次

目录

  • 前言
  • 区间选点
    • Code
  • 最大不相交区间数量
    • Code
  • 区间分组
    • Code
  • 区间覆盖
    • Code


前言

贪心真是玄学,规律全靠猜,证实靠样例!


区间选点

给定 NNN 个闭区间 [ai,bi][a_i,b_i][ai​,bi​],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。

输出选择的点的最小数量。

位于区间端点上的点也算作区间内。

输入格式
第一行包含整数 NNN,表示区间数。

接下来 NNN 行,每行包含两个整数 ai,bia_i,b_iai​,bi​,表示一个区间的两个端点。

输出格式
输出一个整数,表示所需的点的最小数量。

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109−10^9≤a_i≤b_i≤10^9−109≤ai​≤bi​≤109

输入样例:

3
-1 1
2 4
3 5

输出样例:

2

思路:对于所有区间按照右端点进行一遍sort,然后从第一个区间开始,选择右端点作为那个要包含的其中一个点choice,因为这个choice很有希望能处在往后面几个区间的范围里,这样就减少了要选择点的次数,如果遇到某个区间使得choice不在其里面,那就更新一下choice为当前这个区间的右端点,同时点的个数+ 1,按照这个步骤循环往复遍历所有区间… …

Code

#include 
#include 
#define l first
#define r second
using namespace std;
typedef pair PII;const int N = 1e5 + 10;PII R[N];
int n, choice, ans = 1;bool cmp(PII a, PII b){return a.r < b.r;
}int main(){scanf("%d", &n);for(int i = 0;i < n;i ++){int a, b;scanf("%d %d", &a, &b);R[i] = {a, b};}sort(R, R + n, cmp);        //每个区间按照右端点排序/*如果将每个区间的右端点作为被选中的那个点  那么对于后面的区间来讲,再需要新增的点的频率可能会降低首先选择第一个区间右端点*/choice = R[0].r;        for(int i = 1;i < n;i ++){if(R[i].l <= choice && choice <= R[i].r)            continue;       //这个区间被“照顾”到了  可以不用管了choice = R[i].r;        //这个区间跟前面的没有交集了  要更新右端点ans ++ ;        //多选择一个点}cout << ans << endl;return 0;
}

最大不相交区间数量

给定 NNN 个闭区间 [ai,bi][a_i,b_i][ai​,bi​],请你在数轴上选择若干区间,使得选中的区间之间互不相交(包括端点)。

输出可选取区间的最大数量。

输入格式
第一行包含整数 NNN,表示区间数。

接下来 NNN 行,每行包含两个整数 ai,bia_i,b_iai​,bi​,表示一个区间的两个端点。

输出格式
输出一个整数,表示所需的点的最小数量。

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109−10^9≤a_i≤b_i≤10^9−109≤ai​≤bi​≤109

输入样例:

3
-1 1
2 4
3 5

输出样例:

2

关于这道题,其实在以前有一个很实际的例子介绍过:洛谷 P1803 - 凌乱的yyy / 线段覆盖。
那么仍然是右端点sort一遍,然后挨着找最多的不相交区间数量,其实可以注意到跟上题思路虽说不一样,但最终带来的结果却是一样的,因此完全可以用同样的代码(下面微调整了一下)。

Code

#include 
#include 
#include 
using namespace std;const int N = 1e5 + 10;struct ran{int l, r;bool operator< (const ran &t)const{return r < t.r;}
}Range[N];int n, ed;int main(){cin >> n;for(int i = 0;i < n;i ++){int a, b;cin >> a >> b;Range[i] = {a, b};}sort(Range, Range + n);int ans = 0, ed = -2e9;for(int i = 0;i < n;i ++)if(ed < Range[i].l){ans ++;ed = Range[i].r;}cout << ans << endl;return 0;
}

区间分组

给定 NNN 个闭区间 [ai,bi][a_i,b_i][ai​,bi​],请你将这些区间分成若干组,使得每组内部的区间两两之间(包括端点)没有交集,并使得组数尽可能小。

输入格式
第一行包含整数 NNN,表示区间数。

接下来 NNN 行,每行包含两个整数 ai,bia_i,b_iai​,bi​,表示一个区间的两个端点。

输出格式
输出一个整数,表示所需的点的最小数量。

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109−10^9≤a_i≤b_i≤10^9−109≤ai​≤bi​≤109

输入样例:

3
-1 1
2 4
3 5

输出样例:

2

思路:按照左端点从小到大sort一遍,然后每组记录一个当前组内所有区间里最大的那个右端点值Max_r,方便后面的区间判断适不适合加入到这个组里来。也就是

  • 遍历每个区间,如果有某个组的Max_r < Range[i].l,说明该区间可以加到里面去,因此更新一下这个组的Max_r为Range[i].r意味着已经加入了。
  • 由于可能有很多组都满足上面那个条件,只需任选一组就可以。
  • 如果不存在满足上面条件的组,那就需要为该区间“另起炉灶”新开一个组。

注意到:遍历每个区间是O(n)O(n)O(n)的,而在每个区间下遍历每个组又是O(n)O(n)O(n)的,所以复杂度就是O(n2)O(n^2)O(n2)的,显然对于10510^5105的数据量是会超时的,所以不妨使用小根堆优化找合适的组这一步,这样一来复杂度就优化至了O(nlogn)O(nlogn)O(nlogn)了。

  • 使小根堆存各个组的Max_r,取堆顶,如果最小的Max_r都不能满足Max_r < Range[i].l那就没有可以满足的了,直接“另起炉灶”;如果堆顶可以满足条件,那就放到堆顶这一组里。总而言之都能一步到位。

Code

#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
#define l first
#define r secondconst int N = 1e5 + 10;PII ran[N];
priority_queue, greater> heap;       //用小根堆存下每个组的Max_r
int n;int main(){cin >> n;for(int i = 0;i < n;i ++){int u, v;cin >> u >> v;ran[i] = {u, v};}sort(ran, ran + n);for(int i = 0;i < n;i ++){if(heap.empty())        heap.push(ran[i].r);else{int tt = heap.top();if(tt < ran[i].l){heap.pop();heap.push(ran[i].r);        //变相改变这个组的Max_r}else        heap.push(ran[i].r);}}cout << heap.size() << endl;return 0;
}

区间覆盖

给定 NNN 个闭区间 [ai,bi][a_i,b_i][ai​,bi​] 以及一个线段区间 [s,t][s,t][s,t],请你选择尽量少的区间,将指定线段区间完全覆盖。

输出最少区间数,如果无法完全覆盖则输出 −1。

输入格式
第一行包含两个整数 sss 和 ttt,表示给定线段区间的两个端点。

第二行包含整数 NNN,表示给定区间数。

接下来 NNN 行,每行包含两个整数 ai,bi,表示一个区间的两个端点。

输出格式
输出一个整数,表示所需最少区间数。

如果无解,则输出 −1。

数据范围
1≤N≤105,1≤N≤10^5,1≤N≤105,
−109≤ai≤bi≤109,−10^9≤a_i≤b_i≤10^9,−109≤ai​≤bi​≤109,
−109≤s≤t≤109−10^9≤s≤t≤10^9−109≤s≤t≤109

输入样例:

1 5
3
-1 3
2 4
3 5

输出样例:

2

思路:按照左端点对区间sort一遍,然后

  1. 对于每个能包含住s(左限制端点)的区间,找到那个有最大r的区间,然后让这个r成为新的s(言外之意原来那个s已经被“照顾”了,现在的r才是新的需要考虑照顾的左限制端点),并让区间数ans ++。
  2. 如果发现找到的r >= t,说明已经把整个要求的限制区间都囊括到了,break。
  3. 如果发现找到的r < s,说明连左限制端点都囊括不到,答案不存在,break。
  4. 下一次要关注的区间直接是有最大r的区间,并重复步骤1。

Code

#include 
#include 
using namespace std;const int N = 1e5 + 10;struct Range{int l, r;bool operator < (const Range &t) const{return l < t.l;}
}ran[N];
int n, s, t;int main(){cin >> s >> t;cin >> n;for(int i = 0;i < n;i ++){int a, b;cin >> a >> b;ran[i] = {a, b};}sort(ran, ran + n);int ans = 0;bool flag = false;for(int i = 0;i < n;i ++){int ed = -2e9;      //ed作为找到的最大那个rint j = i;while(j < n && ran[j].l <= s){      //双指针寻找最大red = max(ed, ran[j].r);j ++;}if(ed < s){        //最大的右端点也不能包含到点s        注意用“<”因为可能s 等于 tbreak;}ans ++;i = -- j;          //循环跳转, -- j是因为上面while执行了一遍多余的j ++s = ed;if(ed >= t){flag = true;break;}}if(flag)        cout << ans << endl;else            cout << -1 << endl;return 0;
}

相关内容

热门资讯

蜻蜓订购APP贵金属订购非法期...   蜻蜓订购APP以"投资平台"名义对外宣传,主打贵金属期货(订购)交易。该平台一方面强调自身"正规...
悟空订购APP非法期货交易欺骗...   近期,有投资者反映,“悟空订购APP”等平台以白银、贵金属订购为名,宣传所谓“高收益”“低门槛”...
小赢淘金APP期货投资骗局,平...   “小赢淘金”之流,最擅长的就是用“注册送现金”、“充值返券”的糖衣炮弹来引流。别天真地以为那是福...
八方淘金APP非法期货交易欺骗...   警惕!八方生财、每日淘金、小赢淘金、悟空订购、蜻蜓订购、斗金订购等APP均涉嫌非法期货交易!  ...
智易购APP贵金属订购交易骗局...   很多人看到“3元起投”“充值送福利”“操作简单”“随时提现”这类宣传,很容易把智易购APP当成普...
喜玛银庄APP商品订购投资骗局...   喜玛银庄APP白银、铂金“现货订购”骗局警示:无资质平台涉嫌非法期货交易,投资者爆仓后如何维权?...
吉鑫乐享APP炒贵金属订购交易...   近期,多名投资者反映在“吉鑫乐享APP”进行贵金属投资时遭遇严重亏损,甚至血本无归。看似正规的“...
易掘金APP虚假期货投资骗局,...   “易掘金”的APP它打着“高收益、灵活投资”的旗号,宣称通过“商品订购”就能轻松赚钱,吸引了不少...
在大吉订购APP订购交易亏损被...   近期,不少投资者反映在“大吉订购App”上投资白银、铂金等商品遭遇严重亏损。该平台宣称提供现货订...
铂银壹号APP商品订购交易亏损...   许多中小投资者误以为网上的“商品现货订购”是合规合法的理财渠道,殊不知这背后隐藏着巨大的合规风险...
兴鑫淘金APP贵金属订购交易亏...   白银、贵金属或其他商品类投资,除国家批准的正规期货交易场所及持牌期货公司外,市面上大量第三方交易...
铂银掘金APP无资质的违规平台...   铂银掘金等平台的投资者,往往是被“注册送现金”“充值返现券”“首单免亏”等广告话术吸引,进而下载...
八方淘金APP订购交易不合规,...   “八方淘金APP”“铂银掘金APP”“铂银壹号APP”等软件被指以“现货订购”为名,实际采用高杠...
在指尖订购APP订购商品亏损被...   指尖订购APP这类平台,表面是“订购交易”,实则是披着电商外衣的非法期货陷阱。绝大多数投资者被蒙...
在犀贝易购APP做商品订购交易...   市面上打着“现货投资”“贵金属交易”旗号的APP并不少,但真正合规、受监管的平台并不多。犀贝易购...
易达淘金APP虚假商品订购交易...   易达淘金APP存在严重的虚假宣传与违规交易行为。该平台打着“商品订购”的旗号,实则通过不合规的交...
大浪淘金APP白银订购亏损被骗...   大浪淘金APP最隐蔽的套路,在于其完全封闭的内盘交易系统。表面上,它宣称与国际贵金属市场接轨;实...
一品好购APP上订购白银出现亏...   一品好购APP原名“一品订购”,运营方为上海宝智未来信息技术有限公司。近期不少投资者反映在该平台...
九州订购APP贵金属订购投资骗...   九州订购APP正通过抖.音、快手、今日头条等平台大量投放投资广告,用“5元起投”“充值返现”“0...
坚锅淘金APP交易软件并不正规...   当前,市面上大量所谓的“现货商城订购”交易软件,早已偏离了正常的实物商品买卖,演变为高杠杆、高手...