概念
反悔贪心 就是 贪心 + 优先队列
重点是找到 把什么放进优先队列中
每次都把扣的血直接扣掉 加的血直接加上 扣的血加入优先队列中（因为最好我只用移动扣血量最大的 移动一个就可以少移几个血量小的）
直到扣的血超过当前血量的时候 反悔 此时把 扣血最多的移动到最后（不用真的移动）然后把血加上 继续向后
本题放入优先队列的就是 扣血量 因为一个扣血大的可以抵很多个扣血少的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| typedef long long ll;
class Solution {
public:
int magicTower(vector<int>& nums)
{
ll hp = 1;
int cnt = 0;
priority_queue<int>q;
if (accumulate(nums.begin(), nums.end(), 0LL) < 0)
return -1;
for (auto &x: nums)
{
hp += x;
if (x < 0)q.push(-x);
if (hp <= 0)
{
cnt ++;
hp += q.top();
q.pop();
}
}
return cnt;
}
};
|
课程有两个衡量标准 第一是 持续时间 第二是结束时间
结束时间早的应该先上 所以对结束时间进行排序
而持续时间应该放入优先队列 因为 一个持续时间长的可以抵很多持续时间短的 所以尽量要上时间短的课
当当前时间大于这节课的结束时间的时候 就可以考虑要不要反悔 去掉之前上的时间最长的课 改为上这节课（如果这节课的时长较短）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public:
int scheduleCourse(vector<vector<int>>& courses)
{
int now = 0;
sort(courses.begin(), courses.end(), [&](vector<int>a, vector<int>b)
{
return a[1] < b[1];
});
priority_queue<int>q;
for (auto &x: courses)
{
int dur = x[0], last = x[1];
if (now + dur <= last)
{
now += dur;
q.push(dur);
}
else if (!q.empty() && dur < q.top())
{
now -= q.top() - dur;
q.pop();
q.push(dur);
}
}
return q.size();
}
};
|
这题放入优先队列的是高度差 因为高度差高的地方用梯子可以省下很多砖头
梯子相当于是一次性无限量砖块 那么就要把梯子放在差距最高的几个地方 维护长为[梯子的数量]的优先队列 表示这几个要用梯子 后面一旦遇到比top大的高度差 就pop出来 换上这个 然后pop出来的就要用砖头 砖头不够的时候就退出 表示最后只能到这里
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders)
{
int n = heights.size();
priority_queue<int, vector<int>, greater<int>>q;
int sumH = 0;
for (int i = 1; i < n; i++)
{
int deltaH = heights[i] - heights[i - 1];
if (deltaH > 0)
{
q.push(deltaH);
if (q.size() > ladders)
{
sumH += q.top();
q.pop();
}
if (sumH > bricks)
{
return i - 1;
}
}
}
return n - 1;
}
};
|