HDU多校第十场 1008 Coins —— 贪心 + 优先队列

题目链接：点我啊╭(╯^╰)╮

题目大意：

    有 $n$ 组硬币，每组硬币有两个 $a_i,b_i$
    要求拿出 $k$ 个硬币最大值为 $f(k)$
    限制一组硬币： $a_i$ 未拿的时候不能拿 $b_i$
    求 $f(1)、f(2)、...f(k)$

解题思路：

    因为有 $b_i$ 的限制，所以局部最优不是全局最优
    但是仔细考虑一下，假设当前拿了 $k$ 个硬币，且是最优的
    考虑怎么拿下一个硬币：
    $①：$直接拿当前可以拿的最大值的那个硬币
    $②：$放回拿的第 $k$ 个硬币，然后拿当前可以拿的最大的那一组硬币

    经思考发现，没有第三种情况，第三种情况已经包含在上面的最优解里
    所以记录一下各种可以拿的硬币及拿到了第几个
    用优先队列维护一下即可

核心：贪心 + 优先队列乱搞

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
int T, n, ans[maxn], th2[maxn], th[maxn];
struct node1{int x, id, th;bool operator < (const node1 &A) const{return x < A.x;}
};
struct node2{int x, y, id;bool operator < (const node2 &A) const{return x + y < A.x + A.y;}
}; 
priority_queue <node1> q1;
priority_queue <node2> q2;int main() {scanf("%d", &T);while(T--){scanf("%d", &n);while(!q1.empty()) q1.pop();while(!q2.empty()) q2.pop();for(int i=1, a, b; i<=n; i++){scanf("%d%d", &a, &b);th2[i] = b, th[i] = 0;q1.push({a, i, 0});q2.push({a, b, i});}int f = 0, prex, preid, a, b;for(int i=1; i<=n*2; i++){while(th[q1.top().id]!=q1.top().th && !q1.empty()) q1.pop();while(th[q2.top().id]!=0 && !q2.empty()) q2.pop();a = q1.top().x;b = (f&&!q2.empty()) ? q2.top().x + q2.top().y - prex : 0;if(a <= b){	//	取 2个 f = 0;ans[i] = ans[i-1] + b;th[q2.top().id] = 2;q1.push({prex, preid, --th[preid]});q2.pop();} else {	//	取 1个 f = 1;ans[i] = ans[i-1] + a;prex = q1.top().x, preid = q1.top().id;q1.pop();if(!th[preid]) q1.push({th2[preid], preid, 1});++th[preid];}printf("%d%c", ans[i], " \n"[i==n*2]);}}
}