首先可知答案的数字具有一定的单调性。考虑使用二分答案的方式。   如何验证：已知这个数字，去区间里面找有多少个数比当前这个数字大，如果数量大于等于m的话证明该数小了，需要向右移动反之向左移动。   在统计区间里面有多少个数比当前的数字大的时候，要注意使用双指针的方式，否则会超时。还有就是要用long long。   //双指针加二分做法。 #include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn&...

订单的编号具有单调性，也就是说可以往二分答案的方向去思考。 已知订单的编号，也就是说在此订单及其之前的订单都能满足。那么如何快速验证订单是否满足就是要解决的问题。 按题中描述以某一天为下标每个订单都有连续几天的租借数量，对于连续区间的加减问题可以联想到差分与前缀和的解法  可以将原来教室数量的列表进行差分，然后可以对区间进行快速加减操作。最后再计算一次前缀和转化回来即可。在转化过程中判断是否有教室数量小于0的一天，如果有那么就证明不满足。   还要注意我将r=m+1，是因为将m出区分开来。因为如果r=m的话根据我的二分写法在m出不满足和满足最后l都是m。所以需要向前走一位用于区分。   //订...

通过二分答案的做法，在这里是二分套牌的数量。那么这就转换成了已知套牌的数量如何去验证能不能达到这么多套牌数。   假设有ABC三种套牌：A：3，B：4，C：5。如果已知套牌数量为x那么对ABC来说数量上就得大于等于x，缺少的就需要用joker来补，那么到底需要多少joker就可以算出来。   对于joker，一个最明显的条件就是必须小于m，毕竟只有m张joker。还有就是题目中说一次套牌只能有一张joker，那么joker最多只能用x次。   要注意在计算过程中会超出long long的范围（虽然题目中给的数据没有超出long long范围）。还要注意二分里面最大要开到多少，不能仅仅开到500...

求最小幸福值的最大值，本题中只需要以答案入手去二分答案即可。 至于如何验证：从第一天开始遍历，如果幸福值小于给定的最小幸福值那么就吃巧克力就完了。  看最后是巧克力被先吃完，还是能够满足贝西每天的幸福值需要。   需要注意的是在记录记录每天吃巧克力的方案的时候前提是需要验证通过。因为最后结果有可能是从不通过的右边移动到左边然后退出循环的。   坑点：这个坑点想半天也没想出来，最后看题解说是巧克力必须吃完。这个只能靠猜，真的服了。。。。   //求最小幸福值的最大值，本题中只需要以答案入手去二分答案即可。 //至于如何验证：从第一天开始遍历，如果幸福值小于给定的最小幸福值那么就吃巧克力就完了。 ...

首先最容易想到的是暴力的四层遍历，时间复杂度为O(n^4)。 对最后一层的遍历可以改成二分查找，时间复杂度为O(n^3logn)。 但上两种方式都会超时。 有四个数字序列，可以联想到先使用二重循环将前两个和后两个序列的所有结果求出来。 然后在根据前一个求出来的序列去二分寻找后一个序列中符合要求的有多少种。  这样的时间复杂度：O(n^2+nlogn)   //首先最容易想到的是暴力的四层遍历，时间复杂度为O(n^4)。 //对最后一层的遍历可以改成二分查找，时间复杂度为O(n^3logn)。 //但上两种方式都会超时。 //有四个数字序列，可以联想到先使用二重循环将前两个和后两个序列的所有结果...

采用二分验证的方式，  验证：先假设没有烘***，那么t分钟过后每件衣服就消耗了t个水分。这时候在使用烘***的话就水每分钟消耗n-1个水分，那么每一件衣服还需要使用多少次烘***就可以计算出来。   然后一共可以使用t次烘***，进行比较即可得到。要注意在计算过程中次数可能超出int的范围，需要开long long。   //采用二分验证的方式， //验证：已知时间，散热器的K，那么就可以算出最大能烘干最大的水分。通过最大水分就可以判断是当前的答案合不合理 #include <bits/stdc++.h> typedef long long&nbsp...

寻找R的最小值，同样可以使用二分验证的方式去做，那么问题就落到了如果验证当前的R可以将草堆全部引爆。  如何验证：从左向右去炸第一问即可，在其中维护一个当前爆炸的最大坐标从而来判断当前这个草堆是不是需要去炸的第一个就可以了。   //寻找R的最小值，同样可以使用二分验证的方式去做，那么问题就落到了如果验证当前的R可以将草堆全部引爆。 #include <bits/stdc++.h> using namespace std; const int maxn = 50000+10; int N, K...

一个寻找最小的尽量大的题目，做这种题目首先要考虑是否可以使用二分验证的方式，因为这种题目的答案在一个单调区间里面寻找。所以可以通过二分答案加一验证的方式快速寻找的答案。   那么要考虑的就是如何验证是否可行，在本题中使用双指针的策略。last保存上一个石头，如果长度符合那么就让last和i都增加，因为已经大于验证的答案了i再向右移动都一定正确，再验证就没有意义了。如果长度不符合，那么就不移动last，这样正好将这个石头错开（相当于删除了）。   #include <bits/stdc++.h> using namespace std; const&nb...

//使用前缀和记录在什么时候音符开始演奏，然后在通过二分查找值的范围即可。 #include <bits/stdc++.h> using namespace std; const int maxn = 50000+10; int N, Q; int ying_fu[maxn]; int find_pos(int x) {     int l = 1, r =&nbs...

一个二分查找的基本题，不同的是需要寻找范围。那么就是要找第一个符合的最小的数，最后一个符合的最大的数。这样可以通过返回下标直接相减加一得到数量。在寻找最大的数的最大下标的时候需要mid = (l+r+1）/2。因为如果相等会让l = mid。但(l+r)/2会偏向于l处。在相邻的时候会出现不变的情况导致死循环。   细节：需要判断是否与题中所给区间有无交际，如果没有的话直接输出0，否则再使用查找函数去查找的话会找到第一位和最后一位停止的，返回的结果不对。   #include <bits/stdc++.h> using namespace std; c...

本题字符串中符号最大达到100000，那么只用递归的方式去求解表达式的话就需要100000层的递归（会超时）。那么可以回到后缀表达式的思路。   使用op栈保存符号，num栈保存数字。在计算过程中遇到*就进行计算后把计算的结果压栈。重复这个过程就可以了。   要注意：题目要求当答案长度大于4位时，输出后四位。而且题目中给的数据范围是2^31-1，在计算过程中也会超过数据类型范围。采用取余的性质在计算过程中取余。   #include <bits/stdc++.h> typedef long long ll; using namesp...

本题考察快速幂算法和快速乘算法，快速幂算法可以正着进行也可以反着进行，在这里采用正着进行倍增的思路。   以2^10为例，其中指数10可以变成二进制1010，也就可以变成2^(2^3)+2^(2^1)。2的出现也就意味着可以使用倍增的思路去求解。   也就是将指数变成二进制进行挨个计算，在计算过程中维护temp的倍增。这样如果当前二进制位等于1的时候可以直接乘于temp。   另外在本题当中由于在相乘的过程中会超出long long的范围，所以还需要使用快速乘算法，将乘法变成多个加法。使用递归去实现。   代码：   #include <bits/stdc++.h> ty...

本题与经典汉罗塔很像，但由于只能相邻移动的特点有导致移动方法有些不同。   假设只有两个盘子：由于只能相邻移动所以不能先从A到B，再A到C，因为A到B之后中间那根柱子由于最上面的盘子挡着呢，所以过不去。   那么就只能通过B柱子一次性移动到C才可以将下面的盘子从A到B。然后还需要将C上面的盘子借助B移动到A，将C柱子的位置留出来让B上面的大盘子移动到C。   最后让A到C就可以了。   当然这是2个盘子的情况。扩展到n个盘子的情况就是：   先将n-1个盘子从A到C；   再第n个盘子将A到B；   再n-1个盘子将C到A；   再第n个盘子将B到C；   在前n-1个盘子将A到C；   中间...

题目链接：1008-兔子的逆序对_2021秋季算法入门班第二章习题：递归、分治 (nowcoder.com)   本题求逆序对的思路还是按照归并排序的过程去求解，但不同之处在于本题需要不断的变换区间里面数的排列。首先考虑在每一次变换之后都去求解逆序对的数量肯定是会超时的。   然后可以联想到如果在区间发生变化之后快速求出逆序对的个数，即可发现在一个区间里面翻转之后逆序对的个数=区间里面的对数-翻转之前逆序对的个数。   可以列出公式：ans-(r-l+1)*(r-l)/2-2x（ans是逆序对的总个数，x是反转之前区间里面逆序对的个数）。可知2x必然是偶数，那么ans奇偶性的变化就取决于(r-...