首页 > 代码库 > bzoj1572 [Usaco2009 Open]工作安排Job
bzoj1572 [Usaco2009 Open]工作安排Job
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1572
【题解】
这么傻逼的题会想错啊。。。
想到用优先队列维护了但是维护的方向想错了。
按时间排序
用优先队列维护当前p最大的当前时间个。
然后加入 如果不满就加,否则选一个扔掉。最后统计队列中的即可。
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10; const int mod = 1e9+7; # define RG register # define ST static int n; struct pa { int d, p; pa () {} pa (int d, int p) : d(d), p(p) {} friend bool operator < (pa a, pa b) { return a.p > b.p || (a.p == b.p && a.d < b.d); } }p[M]; priority_queue<pa> q; inline bool cmp(pa a, pa b) { return a.d < b.d; } int main() { cin >> n; for (int i=1; i<=n; ++i) scanf("%d%d", &p[i].d, &p[i].p); sort(p+1, p+n+1, cmp); for (int i=1; i<=n; ++i) { if(q.size() < p[i].d) q.push(p[i]); else if(p[i].p > q.top().p) { q.pop(); q.push(p[i]); } } ll ans = 0; while(!q.empty()) { ans += q.top().p; q.pop(); } cout << ans << endl; return 0; }
bzoj1572 [Usaco2009 Open]工作安排Job
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。