在刷题的单身狗很开心

分类

2023河南萌新联赛第（八）场(3) c++(1) 动态规划(5) 差分与前缀和(4) 洪水填法(1) 牛客小白月赛78(4) 牛客练习赛115(2) 牛客练习赛116(2) 算法(1) 算法刷题(2) 题解(176)

/ 注册

全部文章（共201篇）

题解 | #[JSOI2007]建筑抢修#

先按照最晚修理时间进行排序，从最早的开始进行遍历。进来后如果可以达到最晚修理时间那么直接加入即可，如果达不到的话，与我已有的建筑的修理时间进行比较如果修理时间比原有的小的话那么就需要对原来的建筑进行一个调整，如果大的话不变就行，总之是一个一换一的过程，但同时也为后面腾出了更多的修理时间，所以贪心成立...

C++ 贪心堆(优先队列)

2023-09-14

2 379

题解 | #tokitsukaze and Soldier#

本题是一个可后悔的贪心，首先从简单来看，如果单纯根据战力选择可能会因为人数现在而没有达到最优，如果根据人数限制选择，可能会出现极端战力导致错误。但如果两个条件其中之一我们已知的话求解起来就比较简单了，如果我们已知人数限制，那么只需要在所有人数限制超过这个的人里面选最好的几个就行了。这看起来很...

C++ 贪心堆(优先队列)

2023-09-14

2 309

题解 | #[JSOI2010]缓存交换#

本题是一个贪心问题，关键在于贪心策略如何选择。想要缺失的可能性尽可能少，首先可能就想到丢掉后面出现次数少的，但比起出现次数顺序更加重要。最后得到贪心策略为：去掉最近的。在本题中算法如何实现也不容器，应当保存下标才方便，否则如果相同的时候会有不必要的麻烦。 #include&nbs...

C++ 贪心

2023-09-14

3 383

题解 | #Running Median#

使用对顶堆可解，左边的堆维护中位数前半部分，右边的堆维护中位数后半部分。在新的数进来的时候判断应该插左边还是右边，然后对左右如果差值超过1进行调整。这样要么左堆的顶端是中位数，要么当左右相同大小的时候就是两个堆顶的数取平均数。 //对顶堆，以左边为承载多出来的那个中间数的堆 #inclu...

C++ 对顶堆优先队列

2023-09-13

3 450

题解 | #第k小#

//建立两个堆，一个大根堆，一个小根堆。从K处劈开 #include <bits/stdc++.h> using namespace std; int n, m, k; const int maxn&nb...

C++ 优先队列堆

2023-09-13

5 344

题解 | #Largest Rectangle in a Histogram#

限制大小的关键在于某一个矩形向左可以到什么地方，向右可以到什么地方。如果可以得知这个长度，再乘以该矩形的高度就是我们所需要的该矩形的最大面积。然后枚举求出所有矩形的最大面积，求最大的那一个就可以了。那么如何去向左和向右寻找最远的地方呢？我们可以将问题转换成找最近的阻挡点，那么就可以使...

C++ 栈

2023-09-12

1 374

题解 | #Look Up#

类似于滑动窗口，但比滑动窗口要简单。在本题中因为是向坐看（其实是向高下标的方向看）。所以从后向前去遍历，如果栈为空那么直接加入即可，如果当前的数比栈顶的数要大，那么栈顶里面的数不可能成为那个被仰望的了，所以弹出，又因为可能不止一个，所以用循环。如果比栈顶数要小证明还有可能称为那个背仰望的，接着加入栈...

C++ 栈滑动窗口

2023-09-12

2 354

题解 | #Sliding Window#

本题是一个滑动窗口问题，在移动过程中改变的是第一个数被丢掉和下一个数加进来。那么可以建立一个队列，如果当前进来的这个数比前面的某些数要大的话就需要出队，因为由于这个更大的数的存在前面的数就不可能变成最大的数。那么就需要直接从队列里面删除。如果第一个在窗口移动的时候被丢掉了同样也要删除。如果新加进来的...

C++ 双向队列滑动窗口

2023-09-12

1 338

题解 | #[NOIP2016]蚯蚓#

使用优先队列会超时，因为优先队列的内部实现是小根堆或大根堆。并不是O(N)的时间复杂度。在本题当中可以使用三个队列，一个原始序列排序好的队列，一个切完后左边蚯蚓的队列，一个切完后右边蚯蚓的队列。这样只需要每次比较队首的蚯蚓长度就可以得到刽子手需要去砍的蚯蚓。然后本题的输出比较麻烦，需...

C++ 队列

2023-09-11

4 470

题解|#Antiamuny wants to leaern binary search again#

将题目中的二分写法做一个小小的改变即可，注意：一定要将左边移动，不然会损失一些次数。 #include <bits/stdc++.h> using namespace std; int f(int l, int&nbs...

C++ 二分模拟

2023-09-11

1 345