在刷题的单身狗很开心

题解

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

/ 注册

全部文章 / 题解（共18篇）

题解 | #牛牛国的战争#

//面对每一次的敌人，如果有可以将敌人打到的军队那么选刚好防御力够存活下来的那一个。 //如果能打到敌人但是确是去送死的话，那么选防御力最差的那一个。 //如果不能打倒敌人那么直接宣布失败就可以。 //首先使用结构体数组对其进行相应的排序，然后将攻击力满足的防御力放入multiset（利用set里面...

C++ 贪心 STL

2023-10-04

2 510

题解|#小A与任务#

首先最任务进行排序，首先按截止时间进行排序然后按z的值从大到小进行排序。按截止时间进行排序是因为如果过了截止时间那就相当于没完成，所以比较优先，那之后为什么按照z的值进行排序呢？因为z的值大能耗费更小的钱去买。在做任务的过程中如果前面任务的时间相加超过当前任务的截止时间了，就得需要向前面的任务以及他...

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

2023-09-24

1 423

题解|#网络优化#

题目链接：1010-网络优化_2021秋季算法入门班第五章习题：优先队列、并查集 (nowcoder.com) 一开始想到了放炸弹烧草那道题，以为可以先对l进行排序使其尽量能走多少人就走多少人的贪心策略。但我忽略了走的并不一定是一个连续的区间。有可能因为走多了而导致浪费了一些。那么从人...

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

2023-09-22

1 439

题解 | #背包#

做这道题的时候一开始想到了对顶堆但发现如果根据输入逐步使用对顶堆的话，不好实现最优的选择。看了题解才知道这不是一道对顶堆的题目，可以使用对物品的价值进行排序，然后某个物品能否作为中位数可以通过向左取(m-1)/2个物品，向右取(m-1)/2个物品。取左右物品的最小重量总和然后加上中位数可以判...

C++ 堆(优先队列) 前缀和二分 C++ 贪心二分优先队列前缀和

2023-09-20

2 441

题解 | #任务#

本题是一个贪心问题，如果进行任务和机器的匹配是我们要考虑的问题。首先如果按照任务的要求去找机器的话，那么任务可以先定时间，去机器里面找时间上符合要求的机器，然后肯定是要选择满足难度级别的最小的那一个，这样可以为后面的任务腾出最大的空间。但题目要求数量和利润都达到最大，但从利润的计算公式上看，时间的占...

C++ STL 贪心

2023-09-15

3 447

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

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

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

2023-09-14

2 359

题解 | #tokitsukaze and Soldier#

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

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

2023-09-14

2 285

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

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

C++ 贪心

2023-09-14

3 371

题解 | #起床困难综合症#

通过一个全0 和全1的二进制int数进行一系列操作可以得到每一位上如果填0或1的时候是什么样的情况。然后从前向后遍历二进制位，如果当前位可以由0变化成1那么可以直接将结果伤害的这一位填上1，如果只能由1变成1那么就需要判断当前的位上的原始伤害会不会超过范围，如果超过了就意味着无法填1。 #in...

C++ 贪心

2023-08-26

0 383

题解 | #兔子的区间密码#

以最先不同的为开始，往后都可以取到1 #include <bits/stdc++.h> typedef long long ll; using namespace std; // inline ll&n...

C++ 贪心

2023-08-26

0 325