首页 > 其他分享 >AcWing905.区间选点

AcWing905.区间选点

时间:2023-05-22 19:44:27浏览次数:41  
标签:选点 arr res cnt AcWing905 端点 区间 input

题目详情

知识点

区间贪心
为什么叫贪心呢?

——短视,每次只是在看眼前的东西,在眼前的决策中选一个最优解。而贪心就是根据这种策略能够走到全局最优解的方法【如果用函数图像来表示就是一个单峰的图】

贪心的普遍方案

一般来说贪心问题没有思路的时候我们可以先随便试一下,再去举一些例子看自己的方法有什么缺漏,如果没什么问题的话就去证明一下这个方法的有效性

思路

自己的思路:(错误的仅供参考)

对于这种题不知道为什么总是下意识想按照左端点排序,然后再一个个判定,但是这样会忽略一种情况

对于上图这种情况,我会默认放在较大区间的右端点处,但是这种情况对于区间[-8,4]里面是没有点的!

n = int(input())
arr = []
for i in range(n):
    l,r = map(int,input().split())
    arr.append([l,r])
arr.sort(key=lambda x:x[0])
res = 1
l = arr[0][1]
print(l)
for i in range(1,n):
    if arr[i][0] > l:
        res += 1
    l = max(l,arr[i][1])
print(res)

正确的思路

区间贪心问题的分析:无外乎就是排序(按左端点or右端点or双关键字)

先试想一个方法:

  • 将每个区间按右端点从小到大排序
  • 从前往后依次枚举每个区间
    • 如果当前区间中已经包含点,则直接pass
    • 否则,选择当前区间的右端点

好的,我们现在找到了一个算法,现在我们得证明该算法的有效性

我们可以利用数学中的证明方法:要证明A=B

就要证明①A≥B;②A≤B。我们遵循这个思路进行证明

用ans表示最终答案,用cnt表示通过该算法求出的答案

首先每个区间一定都包含一个点,因此当前选点方案肯定是一组合法方案

本题的最优解指的是:所有合法方案中的最小值,所以有①ans≤cnt

对于算法第二步的第二种情况,对所有没被pass的情况

第一个区间肯定被选了,那下一个被选的点肯定是与当前这个区间没有任何交点的区间,如下图所示

然后我们依次找到了cnt个点,对应cnt个区间,是从左到右互不相交的区间

所以如果要覆盖这些区间,那至少要用cnt个点,而题目要求我们所选的点要覆盖所有区间(一定包括这些互不相交的区间)

所以可选方案一定要包括这些点②ans≥cnt

因此,ans=cnt,方法可行

代码

n = int(input())
arr = []
for i in range(n):
    l,r = map(int,input().split())
    arr.append([l,r])
arr.sort(key=lambda x:x[1])
res = 1
r = arr[0][1]
for i in range(1,n):
    if arr[i][0] > r:
        res += 1  # 放一个点
        r = arr[i][1] # 放在右端点
print(res)

自己思路的优化

以上是比较好理解的思路,但其实用左端点排序(就是我自己的思路的方法)也可以,但是在更新的过程中要取最小值。
因为左端点排序的话,一个大区间会存在多个小区间;那么要想点数尽可能少,那么就选择小区间的右端点作为覆盖点,小区间可以覆盖大区间,但是不能覆盖大区间内另一个没有重复区域的小区间,所以要维护最右端点值

n = int(input())
arr = []
for i in range(n):
    l,r = map(int,input().split())
    arr.append([l,r])
arr.sort(key=lambda x:x[0])
res = 1
r = arr[0][1]
for i in range(1,n):
    if arr[i][0] > r:
        res += 1
        r = arr[i][1]
    else:
        r = min(r,arr[i][1])
print(res)

标签:选点,arr,res,cnt,AcWing905,端点,区间,input
From: https://www.cnblogs.com/JaineCC/p/17421545.html

相关文章

  • 二分查找的要点,区间能缩小为一个点
    二分查找的要点就是让目标区间不断缩小直至为一个点。这同样是一些分治算法的目标,比如快速排序,我们的目标是区间缩小为一个点,如果你不能理解这个问题,那么通常会在剩余最后两三个数的时候混乱。我们在二分查找的时候,要不断通过leftrightmid的更新去达到我们最终目标;如果我们的......
  • 区间贡献法
    1.英雄的力量(数学规律)2.子数组的最小值(最大值)之和3.子数组的最小乘积的最大值单调栈+前缀和classSolution{public:intmaxSumMinProduct(vector<int>&arr){constintmod=1e9+7;//由于是正数,只用计算最大区间即可//先求最小值......
  • 【P4331 [BalticOI 2004]】Sequence 数字序列 题解(左偏树维护动态区间中位数)
    左偏树维护动态区间中位数。传送门P4331BalticOI2004Sequence数字序列。Solution1我的思路和题解前半部分完全重合了((如果按照单调不增去分割\(a\)序列的话,对于每一段我们能很简单地得出它的最佳答案:中位数。发现严格单调很难做,很难拿捏,考虑对\(a\)序列的每一项都进......
  • 435. 无重叠区间(贪心)
    labuladong题解思路难度中等963给定一个区间的集合 intervals ,其中 intervals[i]=[starti,endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 。 示例1:输入:intervals=[[1,2],[2,3],[3,4],[1,3]]输出:1解释:移除[1,3]后,剩下的区间没有重......
  • mysql update语法 竟然不支持limit区间限制
    首先查询可以这样写,没毛病的SELECT*fromaLIMIT1000,2000 1.然后看一个不是区间的limit,更新满足条件的前1000条,没问题updateaseta.imp_date=4wherea.is_sync=0limit10002.这样写是错误的updateaseta.imp_date=4wherea.is_sync=0limit1001,2000......
  • 区间dp
    ICPCBeijing2017J,PanguandStoneshttp://oj.daimayuan.top/course/8/problem/327题意:有n堆石子,需要合并成一堆,但每次合并必须合并>=L且<=R堆,代价为总和,求最小代价。(n<=100)题解:经典的石子合并是两两合并,而此处是多堆合并,直接枚举所有合并不现实,我们考虑多加一维状态,dp[i]......
  • hdu:LCIS(线段树+区间合并)
    ProblemDescriptionGivennintegers.Youhavetwooperations:UAB:replacetheAthnumberbyB.(indexcountingfrom0)QAB:outputthelengthofthelongestconsecutiveincreasingsubsequence(LCIS)in[a,b].InputTinthefirstline,indicatingt......
  • 树状数组--动态维护区间操作
    树状数组(二元索引树/二元下标树/BinaryIndexedTree,BIT/FenwickTree):树状数组虽名为数组,但从其英文名(BinaryIndexedTree)可看出它本质上是一种被表达为树的数据结构。对于大小为n的序列nums,最基本的树状数组以O(logn)时间复杂度同时支持如下两种操作。1)更......
  • CF1824D LuoTianyi and the Function & 区间历史和模板
    LuoTianyiandtheFunction:LuoTianyigivesyouanarray\(a\)of\(n\)integersandtheindexbeginsfrom\(1\).Define\(g(i,j)\)asfollows:When\(i\lej\),\(g(i,j)\)isthelargestinteger\(x\)thatsatisfies\(\{a_p:i\lep\le......
  • 5-11打卡,交换两个list容器的区间的元素
    10-6编写一个具有以下原型的函数模板:templatevoidexchange(list&11,list::iteratorpl,list&12,list::iteratorp2);该模板用于将l1链表的[p1,l1.end())区间和l2链表的[p2,l2.end())区间的内容交换。在主函数中调用该模板,以测试该模板的正确性。#include<iostream>#incl......