已注销

贪心

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / 贪心（共62篇）

51Nod－1099－任务执行顺序

ACM模版描述题解贪心算法，要想最小，只需要将R和O差最大的那个任务放到最后即可。代码 #include <iostream> #include <cstdio> using namespace std; const int INF = 0x3f3f...

2021-05-22

0 412

51Nod－1163－最高的奖励

ACM模版描述题解这是一道十分不错的贪心问题，有O(nlogn)和O(n*α(n))解法。 One O(nlogn)算法：将最晚结束时间升序排序，第n个任务最晚时间如果大于已经消耗的时间，则可以算入总和，若不大于可以尝试替换掉已经算入总和中的最小奖励的任务，条件是这件任务的奖励...

2021-05-21

0 665

51Nod－1418－放球游戏

ACM模版描述题解一道模拟题，AC率之高，令人发指，但是并不是说明这道题很水，毕竟A它的人数基数不大。这里根据题意，需要额外考虑的是当球的个数是1个或者2个时，结果分别是0和1，然后，就需要考虑球放的位置了，当然，这其实是一个烟雾弹，我们只需要每次都尽量往中间放，使两边的球色最杂...

2021-05-21

0 426

51Nod－1475－建设国家

ACM模版描述题解第一感觉，这道题很像最高的奖励这道题的思路，只是不能用优先队列神马的简单维护。今天花了些许时间A掉了它，细节繁多，关键是两点，第一：最右端点可以连接两个城市，第二：可以在规定时间内往返首都的城市的选与不选。针对这两个问题，首先进行排序，将hi从大到小排列...

2021-05-21

0 463

51Nod－1625－夹克爷发红包

ACM模版描述题解做这道题，有些懵逼了我，因为一开始使用的方法是纯粹的贪心，但是偏偏有一组数据挂掉了，傻傻A不过去…… 这个解法，是将行和列并在一起贪心，可能是因为行和列数据交叉，产生了后效应性，所以有的数据会挂掉。然后，采用的枚举加贪心AC了。因为行数最大为10，所以可以...

2021-05-21

0 394

51Nod－1191－消灭兔子

ACM模版描述题解一道思路上很水，但是细节需要注意的题。比较常规的有两种思路，都是贪心算法： 1、从每只兔子考虑，用未被使用的价值最小的箭射死它； 2、从每只箭考虑，杀死未被杀死的血量最大的兔子。这道题可以用优先队列(代码One，第一种思路)做，也可以使用二分(代码Two...

2021-05-21

0 439

51Nod－1281－山峰和旗子

ACM模版描述题解猛一看题，和51Nod的1285题很像，连配图都一样，仔细一看，还是有区别的，可是，这道题数据有些水，贪心暴力（代码One）就能解，这样子看来，比1285还简单些，当然也有稍微高效些（代码Two）的解法，使用二分优化。代码 One： #include <...

2021-05-21

0 404

51Nod－1316－回文矩阵

ACM模版描述题解这道题搞得我挺焦虑的，矩阵不大，可以暴力枚举。枚举所有的组合，然后在这些组合内部，先固定选取的行，然后遍历列，保证遍历完后，选取的行都是回文的；然后再固定选取的列，接着遍历行，保证遍历完后，选取的列都是回文的；每种组合得到一个需要改动的次数，从所有结果中选取最优...

2021-05-21

0 740

51Nod－1337－翻转游戏

ACM模版描述题解首先逐关进行两次遍历，遍历第一遍，查找到开关操作是否需要，再遍历一遍，检索?，如果遇见?则向下一组查找对应位置，直到查找到最后一关卡，或者不是?的关卡，这时，根据此关卡是否进行相关开关操作来改变后边关卡的对应位置的状态，具体有三大种五小种状态，逐一分析，逐一修正即可...

2021-05-21

0 376

51Nod－1351－吃点心

ACM模版描述题解这道题是贪心问题，分为两种情况贪心：第一种是选取的盒子左边界之和≥X；第二种是C-没有选取的盒子的右边界之和≥X，即C-N个盒子右边界之和+选取的盒子右边界之和≥X。所以，分别按照左边界和右边界进行从大到小排序，逐个选取，获取两个结果，从这两个结果中取最...

2021-05-21

0 348