hzoi044 的博客
优先队列和贪心
hzoi044 @ 2024-7-27 11:08:23

优先队列

优先队列/堆

优先队列又名二叉堆，是特殊的二叉树。二叉堆有两种:最大堆和最小堆
最大堆(大根堆):父结点的键值总是大于或等于任何一个子节点的键值
最小堆(小根堆):父结点的键值总是小于或等于任何一个子节点的键值优先队列：在C++中优先队列默认的是大根堆，如果用小根堆则加入greater. 定义：priority_queue<Type, Container, Functional> Type:数据类型 Container:容器类型（必须是用数组实现的容器，比如vector,deque等，不能用list,STL默认用的是vector， Functional比较方式)

大根堆: priority_queue<int, vector<int>, less<int> >s;less表示按照递减(从大到小)的顺序插入元素小根堆: priority_queue<int, vector<int>, greater<int> >s;greater表示按照递增（从小到大）的顺序插入元素

合并果子(优先队列)

#include<bits/stdc++.h>#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define bug(x) 
  cout<<#x<<"=="<<x<<endl;
  using namespace std;
  typedef long long LL;
  const int N = 1e6 + 10;int n;
  int a[N];
  priority_queue<int, vector<int>, greater<int>>q;
  int main() {	ios;
              cin >> n;	
              for (int i = 1; i <= n; i++) {		cin >> a[i];
                                            q.push(a[i]);
                                           }	
              LL ans = 0;	for (int i = 1; i < n; i++) {		int tmp1 = q.top();	
                                                       q.pop();		
                                                       int tmp2 = q.top();		
                                                       q.pop();		
                                                       ans += tmp1 + tmp2;		
                                                       q.push(tmp1 + tmp2);	}	
              cout << ans << endl;	return 0;}

Running Median（对顶堆）

题目描述: N个数按顺序加入数组，每次加入的时候就输出其中位数。 对顶堆

缓存交换

分析: 堆+贪心

坑点1: 因为要判断当前数是否在缓存区内，可以用一个bool数组，而这个数组要存第i个数是否在缓存区内。即bool[i]的i指第i个数，不能指i这个数在不在缓存区内，因为数最大值为1e9，一维数组开不了这么大。找到第i个数下一次出现的数组nexti同理。
坑点2: 如何贪心？贪心策略？贪心在于，我们当前放的数不在缓存区内，需要先删除一个原来在缓存区的数？如何贪心地删除？ wrong贪心:删除后面出现次数少的那个数 1000 3 12 15 16 14 12 15 14 12 15 后面的数全是16 对于这个样例，如果对于14这个数，用上面的思路一定不删16，而实际上删16最划算，因为你不管删12还是15，在后面的几个数中你都要频繁的删数，而删16的话，紧跟着后面的这几个数不需要删除，后面的一坨16也只需要处理一次即可。 ac贪心:把缓存区中下一次出现最晚的那个给删除了。于是需要一个数组存第i个数的下一次出现在哪里，要一直找最晚，就需要一个堆。
坑点3: 需要维护什么？ bool型数组bool[i]:表示第i个数在不在缓存区 int型数组nexti[i];存第i个数下一次出现的位置堆:q map<int, int> mp num:当前缓存区内元素个数 ans:答案

#include<bits/stdc++.h>
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define bug(x) 
cout<<#x<<"=="<<x<<endl;
  using namespace std;
  typedef long long LL;
  const int N = 1e6 + 10;int n, m;map<int, int> mp;
  bool vis[N];
  int nexti[N];
  int a[N];priority_queue<int> q;
  int ans, num;int main() {	ios;	cin >> n >> m;
                           for (int i = 1; i <= n; i++) {		cin >> a[i];
                                                        }	for (int i = n; i > 0; i--)
                             {		if (mp[a[i]] == 0) nexti[i] = N;
                             else nexti[i] = mp[a[i]];
                              mp[a[i]] = i;	
                             }	for (int i = 1; i <= n; i++) {		
                             if (vis[i] == 0) {			ans++;			if (num < m) {				num++;				vis[nexti[i]] = 1;	
                                                                              q.push(nexti[i]);			} else {				vis[q.top()] = 0;				q.pop();
                                                                                                            vis[nexti[i]] = 1;				q.push(nexti[i]);			}		} else {			vis[nexti[i]] = 1;
                                                                                                                                                                        q.push(nexti[i]);		}	}	cout << ans << endl;
                           return 0;}

堆的题目

堆＋贪心 分析: 我们考虑按s[i]存入vector,从大到小枚举s[i]的值。那么就是在所有>=s[i]的士兵中选v最大的s[i]个。我们可以优先队列维护。因为s[i]是减小的。所以删除的士兵一定在后面用不到。

#include<bits/stdc++.h>#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define bug(x) cout<<#x<<"=="<<x<<endl;using namespace std;typedef long long LL;const int INF = 0x3f3f3f3f;const int inf = 0xc0c0c0c0;const int N = 1e5 + 10;int n;vector<LL> a[N];priority_queue<LL, vector<LL>, greater<LL> > q;LL v, s;int main() {	ios;	cin >> n;	for (int i = 1; i <= n; i++) {		cin >> v >> s;		a[s].push_back(v);	}	LL ans = 0, sum = 0;	for (int i = n; i >= 1; i--) {		for (auto it : a[i]) {			sum += it;			q.push(it);		}		while (q.size() > i) {			sum -= q.top();			q.pop();		}		ans = max(ans, sum);	}	cout << ans << endl;	return 0;}

堆＋贪心 思考贪心的几种策略: (1).按耗时短的贪心虽然耗时短，但是可能截止时间晚，修了这个建筑，反而导致了截止时间早的建筑不能修 (2).按截至时间早的贪心虽然截止时间短，但是可能耗时长，导致本来能抢修后面更多的建筑时间被这一件事占用综上所述，我们每次需要有一个反悔的机会，区重新选择。这个反悔的机会用一个堆来维护，让堆中放每个建筑的耗时，最大的耗时在top。如果发现当前建筑不能在截止时间前做完，那么就去堆中找最大的耗时，是否比它的持续时间要长，如果比它要长就可以把堆中那个建筑替换成当前建筑。由于是替换，所以答案是不变的，而且由于是按截止时间排序，那件事截止时间比它早，持续时间长都可以做完，那替换后仍然可以。

#include<bits/stdc++.h>#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define bug(x) cout<<#x<<"=="<<x<<endl;using namespace std;typedef long long LL;const int INF = 0x3f3f3f3f;const int inf = 0xc0c0c0c0;const int N = 1e6 + 10;int n;priority_queue<int> q;struct ty {	LL s, t;} p[N];bool cmp(ty a, ty b) {	return a.t < b.t;}int main() {	ios;	cin >> n;	for (int i = 1; i <= n; i++) {		cin >> p[i].s >> p[i].t;	}	sort(p + 1, p + 1 + n, cmp);	LL sum = 0, ans = 0;	for (int i = 1; i <= n; i++) {		if (sum + p[i].s <= p[i].t) {			ans++;			sum += p[i].s;			q.push(p[i].s);		} else if (q.top() > p[i].s) {			sum -= q.top();			q.pop();			sum += p[i].s;			q.push(p[i].s);		}	}	cout << ans << endl;	return 0;}

优先队列和贪心