专栏文章

反悔贪心

ssccc_
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkin22
此快照首次捕获于
2025/12/02 03:54
3 个月前
此快照最后确认于
2025/12/02 03:54
3 个月前
查看原文

P2949 [USACO09OPEN] Work Scheduling G

贪心策略：优先完成截止时间小的任务，保证总利润最大化。
维护一个小根堆 qq 存储任务完成后可得的利润，则 qq 的大小就是当前的时间。当 qq 的大小超过当前的截止时间时，弹出队列中最劣的利润。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
	int a, b;
} a[100005];

priority_queue<int, vector<int>, greater<int> > q;

bool cmp(Node a, Node b) {
	return a.a < b.a;
}

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a >> a[i].b; 
	}
	sort (a + 1, a + 1 + n, cmp);
	for (int i = 1; i <= n; i++) {
		q.push(a[i].b);
		if (q.size() > a[i].a) {
			q.pop();
		}
	} 
	int sum = 0;
	while (q.size()) {
		sum += q.top();
		q.pop();
	}
	cout << sum;
	return 0;
}

P4053 [JSOI2007] 建筑抢修

贪心策略：优先完成截止时间小的任务，且保证总抢救建筑的时间最小化。
维护一个大根堆 qq 存储抢救建筑的时间，tt 表示当前的时间，若此时 T2≥t+T1T_2 \geq t + T_1，则抢救此建筑。否则，判断堆顶建筑使用时间是否大于此时的 T1T_1。若大于，则证明此时的答案不优，选择反悔不维修堆顶的建筑，改为维修当前建筑。否则不变。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
	int a, b;
} a[150005];

bool cmp(Node a, Node b) {
	return a.b < b.b;
}

priority_queue<int> q;

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a >> a[i].b;
	}
	sort (a + 1, a + 1 + n, cmp);
	int t = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].b >= t + a[i].a) {
			t += a[i].a;
			q.push(a[i].a);
		} else {
			if (q.top() > a[i].a) {
				t -= q.top();
				q.pop();
				q.push(a[i].a);
				t += a[i].a;
			}
		}
	}
	cout << q.size();
	return 0;
}

P11328 [NOISG 2022 Finals] Gym Badges

与上一题基本一致。只需要注意当前这一关键词即可。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
	int a, b;
} a[550005];

bool cmp(Node a, Node b) {
	return b.a + b.b > a.a + a.b;
}

priority_queue<int> q;

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].b;
	}
	sort (a + 1, a + 1 + n, cmp);
	int t = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i].b >= t) {
			t += a[i].a;
			q.push(a[i].a);
		} else {
			if (q.top() > a[i].a) {
				t -= q.top();
				q.pop();
				q.push(a[i].a);
				t += a[i].a;
			}
		}
	}
	cout << q.size();
	return 0;
}

P3545 [POI 2012] HUR-Warehouse Store

贪心策略：优先完成数量小的顾客的要求。
维护大根堆 qq 存储顾客的数量要求。当当前数量储存不够时，拿出堆顶的需求交换即可。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n;

struct Node {
	int a, b;
	bool operator < (const Node &nxt) const {
		return b < nxt.b;
	}
} a[550005];

priority_queue<Node> q;
set<int> s;

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].a;
	}
	for (int i = 1; i <= n; i++) {
		cin >> a[i].b;
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		sum += a[i].a;
		if (sum >= a[i].b) {
			sum -= a[i].b;
			q.push({i, a[i].b});
		} else if (!q.empty() && sum < a[i].b && q.top().b > a[i].b) {
			sum += (q.top().b - a[i].b);
			q.pop();
			q.push({i, a[i].b});
		}
	}
	cout << q.size() << '\n';
	while (!q.empty()) {
		cout << q.top().a << ' ';
		q.pop();
	}
	return 0;
}

U546879 股票交易 及 CF865D Buy Low Sell High

贪心策略：Buy Low Sell High
维护小根堆 qq 存储价钱方便后面反悔。
首先每天要花 aia_i 的钱数买下一股。
接着，因为需要遵循 Buy Low Sell High 的原则，所以应该是之前买入最便宜的要最大利益化卖出。所以，若当前的价钱比之前的价钱还要高，就将两者交换，并且再压入队列。因为此时是代表之前的价钱的一股股票。
CPP
#include <bits/stdc++.h>
#define int long long

using namespace std;

int n, sum;
priority_queue<int, vector<int>, greater<int> > q;

signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		q.push(x);
		if (q.top() < x) {
			sum = sum - q.top() + x;
			q.pop();
			q.push(x);
		}
	}
	cout << sum;
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...