当前位置: 首页> 财经> 金融 > 手机端网站建设公司_ui设计难学吗_竞价_行业网站有哪些平台

手机端网站建设公司_ui设计难学吗_竞价_行业网站有哪些平台

时间:2025/7/11 7:50:15来源:https://blog.csdn.net/qq_61422664/article/details/146054946 浏览次数:0次
手机端网站建设公司_ui设计难学吗_竞价_行业网站有哪些平台

参考:【学习笔记】反悔贪心 - RioTian


什么是反悔贪心?

反悔贪心,就是可以回溯的贪心,一般题目我们能使用正常贪心的情况是很少的,因为我们只考虑了局部最优解,我们不能保证局部最优解是最后的最优解,就像买股票,万一后面又涨了呢,那我肯定就要后悔了(

总之,对于此类问题,我们将使用反悔贪心来解决


反悔堆

对于某些问题我们将采用最大/小堆来当作中介,以下介绍几种模型

一.“消耗单位时间得非单位价值”求最优解问题

P2949 [USACO09OPEN] Work Scheduling G - 洛谷

思路:

每次我们都可以消耗单位时间来得到 P[i] 的利润,当总消耗时间超过 D[i] 那我们便不能够选取了 P[i]了,对于此题,正常贪心肯定不行,那我们就考虑反悔贪心

首先我们将所有工作按结束时间升序排序,然后我们用一个最小堆优先队列来存储所选的 P[i],那么对于第 i 个工作我们可以有以下情况

①.如果当前的时间小于等于 work[i] 的截至时间

对于这种情况,我们肯定是直接选比较好(贪心),同时将 P[i] 存储到队列中,以便后续反悔

(此时记得将时间t++,因为我们是真正选了)

②.如果当前的时间大于 work[i] 的截至时间

那我就看堆顶的 P 是否大于 P[i],如果大于,那我们肯定就要反悔了,毕竟选这个更好,同时再将答案加上二者的差值

(此时时间t就不需要增加了,因为我们是撤销了之前的操作,由于消耗时间都是单位时间,所以相当于没增加也没减少时间)

代码:

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlpriority_queue<int,vector<int>,greater<>> pq;struct work
{int time, val;
};void solve()
{int n;cin >> n;vector<work> wk(n);for (int i = 0; i < n; i++){cin >> wk[i].time >> wk[i].val;}sort(wk.begin(), wk.end(), [](work a, work b) {return a.time < b.time; });ll ans = 0;for (int i = 0,t=1; i < n; i++){if (t <= wk[i].time){pq.push(wk[i].val);ans += wk[i].val;t++;}else{int x = pq.top();if (x < wk[i].val){pq.pop();pq.push(wk[i].val);ans += wk[i].val - x;}}}cout << ans;
}
int main()
{cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

P3093 [USACO13DEC] Milk Scheduling S - 洛谷

思路:

其实和上题一摸一样(不知道为什么难度还不一样)

代码:

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlstruct MyStruct
{int g, d;
};void solve()
{int n;cin >> n;vector<MyStruct> cow(n);for (int i = 0; i < n; i++){cin >> cow[i].g >> cow[i].d;}priority_queue<int,vector<int>,greater<>> pq;sort(cow.begin(), cow.end(), [](MyStruct a, MyStruct b) {return a.d < b.d; });ll ans = 0;for (int i = 0, t = 1; i < n; i++){if (t <= cow[i].d){pq.push(cow[i].g);ans += cow[i].g;t++;//真正选了,所以要加时间}else if (!pq.empty()){//反悔操作,相当于撤销原来操作,不增加时间int x = pq.top();if (x < cow[i].g){pq.pop();pq.push(cow[i].g);ans += cow[i].g - x;}}}cout << ans;
}
int main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

二.“消耗持续时间得单位价值”求最优解问题

P4053 [JSOI2007] 建筑抢修 - 洛谷

思路:

我们可以像第一类模型一样,我们可以也先按截至时间升序排序,同时我们也用一个优先队列来当中介控制反悔,那么显然,此时我们每个选择都只能得到单位价值,所以我们优先队列就要按照最大堆排序了,且是按每个选择得消耗时间降序排序

为什么?很显然,得X单位价值消耗的时间越少越好,这样才能给后续留有更大的选择空间

所以对于此题,我们可以先升序排序所有任务,然后定义一个所消耗的时间sum,接着枚举所有任务,每次都考虑先选,然后再考虑要不要反悔,那么就有以下情况

①.当前总时间小于等于该任务的截至时间

此时我们肯定要选(贪心)

②.当前总时间大于该任务的截至时间

此时我们就直接将堆顶弹出即可,因为堆顶是耗时最多的元素,同时我们是因为加入新元素才超时的,以此肯定是去除耗时最多的元素最好

而且我们这种先选再考虑的方法也方便了我们反悔,因为可能堆顶最大元素可能就是我们刚刚加入的,所以不需要再比较了

代码:

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlstruct MyStruct
{int t1, t2;
};void solve()
{int n;cin >> n;vector<MyStruct> bulid(n);for (int i = 0; i < n; i++){cin >> bulid[i].t1 >> bulid[i].t2;}sort(bulid.begin(), bulid.end(), [](MyStruct a, MyStruct b) {return a.t2 < b.t2; });ll ans = 0, sum = 0;priority_queue<int> pq;for (int i = 0; i < n; i++){sum += bulid[i].t1;pq.push(bulid[i].t1);if (sum <= bulid[i].t2){ans++;}else{sum -= pq.top();pq.pop();}}cout << ans;
}
int main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

反悔自动机

相比于反悔堆,反悔自动机更加高级一点,它能够自动的维护我们反悔的操作,通常适用于带限制的决策问题上,不过得想出一种策略以便我们代码执行

CF865D Buy Low Sell High - 洛谷

思路:

对于此题,由于我们只能买一股和卖一股,我们可以考虑以下情况

假如我们每一股都买,那我们考虑如何卖出才最好

显然,如果 x < y 那么此时我们卖出肯定是赚钱的,所以遇到大于自生卖出肯定是赚的

那假如有以下情况呢?

如果 x < y < z,此时如果我们卖出的是 x y这一组合,肯定是不如卖出 x z这一组合的

但是我们之前假设每一股都买了,也就是说我们会这样卖出 y - x + z - y,其实就是z - x

我们注意到y其实是无所谓的,那我们就可以设计一个策略来实现反悔自动机

首先我们先买入股票(这个用作贪心),然后我们判断优先队列中是否有比当前股票大的,

如果有的话,那我们就卖了,同时买入当天的(便于后续反悔)

这样的话每次遇到更好的,我们都能用中间值换取更多的钱

代码:

#include <iostream>
#include <algorithm>
#include<cstring>
#include <iomanip>
#include<cctype>
#include<string>
#include <set>
#include <vector>
#include <cmath>
#include <queue>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <utility>
#include <array>
#include <tuple>
using namespace std;
#define ll long long
#define yes cout << "YES" << endl
#define no cout << "NO" << endlvoid solve()
{int n;cin >> n;priority_queue<int,vector<int>,greater<>> pq;ll ans = 0;for (int i = 0; i < n; i++){int x;cin >> x;if (!pq.empty()){int t = pq.top();if (x > t){ans += x - t;pq.pop();pq.push(x);}}pq.push(x);}cout << ans;
}
int main()
{//cin.tie(0)->sync_with_stdio(false);int t = 1;//cin >> t;while (t--){solve();}return 0;
}

THE END

关键字:手机端网站建设公司_ui设计难学吗_竞价_行业网站有哪些平台

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: