题意
几间房间有各自的温度,每次操作可以对连续的几间房间+1/-1度,请问使每个房间都到达目标温度的最小操作次数
思路
将目标温度减去起始温度后会得到一串数列a,目标就是求使这串数列全部为0的操作次数,由于需要实现区间加,比较容易联想到使用差分来进行操作。
转化为差分数组后,每次操作就可以转化为对于某个位置+1/-1,在对某个位置-1/+1,或者不存在后者(就是位置为数列尾部+1)。
这样就只需要比较到底是+1的次数多还是-1的次数多即可
对一些墙壁进行作画,被作画的墙不会毁掉,只有和一面墙相邻的会被毁掉,每天可以画一面墙,每天画的墙必须和昨天画的相邻,然后会有一面墙被毁掉,每堵墙都有美观分,求使最终剩下的墙美观分能够到达的总和最高的值。
首先只有和一面墙相邻的会被毁掉意思就是从两端开始毁掉,由于每天画一面墙,毁一面墙,那最终是能保留
然后,我们就需要枚举每个起点,来比较以此为起点的连续序列和。其实循环下去每次减一个头元素,再加一个尾元素也可以。但是这边用前缀和来处理,每个连续序列和的计算公式为
m份订单,每份订单需要从s天到t天租借d个教室,每天都有r个教室可供租借,每个订单含顺序执行,不需要考虑每天是否需要更换租借教室,求从哪份订单开始会供不应求
显然由于订单的不断积累,每天租借的教室数量保证会持续上涨,满足了单调性,再看一下时间复杂度,1e6的话O(nlogn)能卡,很自然的可以想到二分答案的做法。
二分的难点主要在check,但是二分可以O(n)的来处理,那么我们可以将当前需要check的前x个订单内容加起来,再去查看每天是否有超出可租借范围的。这样思路上没问题,但是前x个订单内容加起来如果直接暴力执行的话,每天都加上某个值显然时间复杂度过高,这种区间加有两种处理方法,一种是直接上数据结构,无脑套线段树,另一种就是通过差分把区间加改为单点加,这样时间复杂度就没有问题了。
最早接触二分一般都是从二分查找开始,对于一串有序数列(假设单调递增),如果中间值小了就往右半边找,如果中间值大了就往左半边找。
代码如下(此处为找最后一个等于x的数,如果没有x则为大于x的第一个数):代码为什么这么写后面会讲
1 | int l=1,r=n; |
显然对于二分不可能只局限于二分查找,我们经常会遇到对于答案进行二分的情况,将if语句中的mid<=x换成check(mid),就是我们常见的二分模板,其实二分查找也可以通过修改check函数得到
单调有序数列
最大值的最小值/最小值的最大值
O(nlogn)的时间复杂度(logn的二分,O(n)的暴力扫一遍)
给定n位字符串,可以对每位进行+1/-1的操作,同时产生相应的进位/退位,9999+1将会变为0000,求变成目标串最少的操作次数
这道题一开始还以为是ICPC沈阳的一道题Luggage Lock,但是那道题可以对连续几位同时进行+1/-1,本题只能对一位处理且会产生进位/退位。
正解为状态机dp,
0:不进位也不退位
1:退位
2:进位
状态转移方程式如下:
由于某一位的改变只会对他的前面一位产生影响,所以需要倒着进行遍历
不需要考虑第一位的改变对于最后一位的影响,显然第一位进位不会更优
Git是一个开源的版本控制系统,可以将Git理解为存储文件的仓库,方便多个用户将文件集中存储到服务器中,或从服务器下载文件副本到本地磁盘。
Git服务并不是简单地存储文件,它会记录每一次文件修改。用户可翻看历史版本的文件,或者删除某些历史修改以还原文件。
例如,在实际开发过程中,会经常出现一些功能回退。就是以前好用的,现在却出现BUG的情况。
通过翻看代码文件的历史版本,可较快速地定位哪次修改影响了这个功能,也能知道团队中哪个人做了这次修改。
那么,Git、Gitlab、GitHub是什么关系呢。
Git可以理解为系统核心,是没有界面的。
Gitlab、GitHub是在Git基础上建设的平台,里面包含Git服务,这些平台拥有更加完善的后台管理网站。也拥有更加丰富的功能,如项目管理、版本视图、权限管理等。
所以我们一般不直接使用或部署Git服务,而是使用功能更加完善的Gitlab、GitHub平台服务,其中Gitlab支持私有化部署。