首页 > 编程语言 >【C++二分查找】2271. 毯子覆盖的最多白色砖块数

【C++二分查找】2271. 毯子覆盖的最多白色砖块数

时间:2024-08-29 18:21:18浏览次数:14  
标签:10 tiles 2271 int 砖块 C++ 瓷砖 carpetLen 毯子

本文涉及的基础知识点

C++二分查找

LeetCode2271. 毯子覆盖的最多白色砖块数

给你一个二维整数数组 tiles ,其中 tiles[i] = [li, ri] ,表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。
同时给你一个整数 carpetLen ,表示可以放在 任何位置 的一块毯子的长度。
请你返回使用这块毯子,最多 可以盖住多少块瓷砖。
示例 1:
在这里插入图片描述

输入:tiles = [[1,5],[10,11],[12,18],[20,25],[30,32]], carpetLen = 10
输出:9
解释:将毯子从瓷砖 10 开始放置。
总共覆盖 9 块瓷砖,所以返回 9 。
注意可能有其他方案也可以覆盖 9 块瓷砖。
可以看出,瓷砖无法覆盖超过 9 块瓷砖。
示例 2:
在这里插入图片描述

输入:tiles = [[10,11],[1,1]], carpetLen = 2
输出:2
解释:将毯子从瓷砖 10 开始放置。
总共覆盖 2 块瓷砖,所以我们返回 2 。
提示:
1 <= tiles.length <= 5 * 104
tiles[i].length == 2
1 <= li <= ri <= 109
1 <= carpetLen <= 109
tiles 互相 不会重叠 。

二分查找

规则二:毯子的左边界和一定和某段瓷砖的左边界(tiles[i][0])对齐。
条件三:能覆盖住x或更多的瓷砖。
本题有解大于等于x    ⟺    \iff ⟺ 规则一下有解大于等于x。下面分别证明:充分性和必要性。
充分性:如果毯子的左边界在某段瓷砖上但不在此段的左边界。左移毯子,左边一定多覆盖一块瓷砖;右边最多少盖住一块瓷砖。
如果毯子的左边界不在瓷砖上,右移。左边覆盖的瓷砖没减少,右边可能增加。
必要性:规则一和本题规则的子集,本题规则下可以选择规则一的方案。
这就是《喜缺全书算法册》的证明一。

先对tiles排序。
枚举各瓷砖段tiles[i],it指向第一个没覆盖的没砖段左端,lower_bound(…tiles[i]+carpetLen),–it 就是被覆盖的最后一段。由于至少盖住了tiles[i],所以–it一定合法。
totals记录个瓷砖段之前的瓷砖总数,不包括tiles[i]。令瓷砖覆盖了tiles[i…j],则覆盖的数量:totals[j] - totals[i] + (end - tiles[j])
end = min(tiles[i]+carpetLen,tiles[j][1]+1) 毯子末端和最后一段瓷砖有三种关系:<=>。

代码

核心代码

	class Solution {
		public:
			int maximumWhiteTiles(vector<vector<int>>& tiles, int carpetLen) {
				sort(tiles.begin(), tiles.end());
				int total = 0;
				vector<int> totals;
				for (const auto& v : tiles) {
					totals.emplace_back(total);
					total += v[1] - v[0] + 1;
				}
				int ret = 0;
				for (int i = 0; i < tiles.size();i++ ) {
					auto j = lower_bound(tiles.begin(), tiles.end(), tiles[i][0] + carpetLen,[&](vector<int>& v1, int val) {return v1[0] < val; }) - tiles.begin();	
					j--;
					const int cur = totals[j] - totals[i] + (min(tiles[i][0] + carpetLen,tiles[j][1]+1) - tiles[j][0]);
					ret = max(ret, cur);
				}
				return ret;
			}
		};

核心代码

vector<vector<int>> tiles;
		int carpetLen;
		TEST_METHOD(TestMethod11)
		{
			tiles = { {1,5},{10,11},{12,18},{20,25},{30,32} }, carpetLen = 10;
			auto res = Solution().maximumWhiteTiles(tiles, carpetLen);
			AssertEx(9, res);
		}
		TEST_METHOD(TestMethod12)
		{
			tiles = { {10,11},{1,1} }, carpetLen = 2;
			auto res = Solution().maximumWhiteTiles(tiles, carpetLen);
			AssertEx(2, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

标签:10,tiles,2271,int,砖块,C++,瓷砖,carpetLen,毯子
From: https://blog.csdn.net/he_zhidan/article/details/141571292

相关文章

  • 线程池ThreadPool, C++
    一、为什么要有线程池?线程池是一种用于管理和复用线程的机制。它可以提高程序的性能和效率,特别是在处理大量并发任务时。线程池中包含一定数量的线程,这些线程可以重复执行多个任务。当有任务需要执行时,可以将任务提交给线程池,线程池会选择一个可用的线程来执行任务。任务执行完......
  • c++1077-1081
    1077:地球人口承载力估计#include<iostream>#include<cstdio>usingnamespacestd;intmain(){inta,b,x,y;cin>>x>>a>>y>>b;doublez=0;z=(b*y-a*x)*1.0/(b-a);printf("%.2lf",z);return0;}1078......
  • C++学习——类当中static关键字的作用
    一、类和对象我们知道类是“行为”和“属性”的集合,我们可以通过类来实例化对象,从而定义对象的“行为”和“属性”。比如:classCar{ Stringbrand; Stringlicense; Stringcolor;}CarToyota;这里定义了“Car”的类,通过“Car”这个类实例化了“Toyota”。那么类当中的......
  • C++学习——访问修饰符
    一、类是什么类是C++当中的一个集合,定义了“属性”,通过类可以实例化对象,此时对象的属性就囊括在这个类当中。比如:classstudent{public: stringName; intages; stringgender}studentXiaoMin;上述代码定义了一个student类,并且通过这个类实例化了对象XiaoMin,XiaoMin......
  • C++火车头修订版
    #pragmaGCCoptimize(3)#pragmaGCCtarget("avx")#pragmaGCCoptimize("Ofast")#pragmaGCCoptimize("inline")#pragmaGCCoptimize("-fgcse")#pragmaGCCoptimize("-fgcse-lm")#pragmaGCCoptimize("-f......
  • 学习笔记3——栈(C++版)
     接下来教大家如何实现一个栈,我们采用单链表的形式。其实说白了就是给单链表写个入栈和出栈的函数就好了。和上一篇文章说的一样,这里说的栈和stack容器是不一样的。如何实现栈1.定义链表节点structStackNode{DataTypeval;ListNode*next;ListNode(DataTy......
  • 学习笔记2——队列(C++版)
    注意了,这里说的队列并不是STL容器库里面的queue。像链表、队列、栈、二叉树其实是一种数据结构,而vector、queue、set等是容器,是不同的概念。队列的实现可以有很多方式,可以用结构体内储存数组来实现,也可以用结构体内储存结构体来实现,我们这里选择后者。如何实现一个队列1.......
  • C++ 设计模式——桥接模式
    C++设计模式——桥接模式C++设计模式——桥接模式1.主要组成成分2.逐步构建桥接模式步骤1:创建实现接口步骤2:实现具体实现类步骤3:创建抽象类步骤4:实现扩展抽象类步骤5:客户端使用3.桥接模式UML图UML图解析4.桥接模式的优点5.桥接模式的缺点6.桥接模......
  • c++数组挑战-字符环
    题目描述:有两个由字符构成的环。请写一个程序,计算这两个字符环上最长连续公共字符串的长度。例如,字符串 ABCEFAGADEGKABUVKLM 的首尾连在一起,构成一个环;字符串 MADJKLUVKL 的首尾连在一起,构成一个另一个环; UVKLMA 是这两个环的一个连续公共字符串。时间限制:1 s内存限......
  • 用c/c++做一个扫雷游戏
    “扫雷”想必80 90年代的都不陌生吧,是当代青年人机必备的益智游戏,今天,我们就用c/c++还原它,记得点赞支持一下,老乔谢谢你们~使用演示设备:1.开发环境 visualstudio2022 或 devc++2.演示系统Windows103.演示课目扫雷游戏效果展示(演示图):上代码:#include<stdio......