BZOJ4977: [[Lydsy1708月赛]跳伞求生

传送门
直接贪心
考虑到 \(n\) 个人的贡献都是 \(a_i\)，另外 \(m\) 个人的贡献都是 \(c_i-b_i\)
首先 \(a_i>b_j\) 的限制不好做，所以将 \(a,b\) 从小到大排序
枚举 \(a_i\) ，每次把小于 \(a_i\) 的 \(b\) 加入优先队列，只要从中间选一个最大的匹配，之后将 \(-a_i\) 加入优先队列，表示可以反悔
代码真的短

# include 
using namespace std;
typedef long long ll;const int maxn(1e5 + 5);int n, m, a[maxn], b[maxn], c[maxn];
pair < int, int > w[maxn];
ll ans;
priority_queue  q;int main() {int i, j;scanf("%d%d", &n, &m);for (i = 1; i <= n; ++i) scanf("%d", &a[i]);for (i = 1; i <= m; ++i) scanf("%d%d", &b[i], &c[i]), w[i] = make_pair(b[i], c[i] - b[i]);sort(a + 1, a + n + 1), sort(w + 1, w + m + 1);for (i = 1, j = 1; i <= n; ++i) {while (j <= m && w[j].first < a[i]) q.push(w[j++].second);if (q.empty()) continue;ans += a[i] + q.top(), q.pop(), q.push(-a[i]);}printf("%lld\n", ans);return 0;
}

转载于:https://www.cnblogs.com/cjoieryl/p/10287073.html

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！