BZOJ4977: [[Lydsy1708月赛]跳伞求生
2024-10-19 00:32:25
传送门
直接贪心
考虑到 \(n\) 个人的贡献都是 \(a_i\),另外 \(m\) 个人的贡献都是 \(c_i-b_i\)
首先 \(a_i>b_j\) 的限制不好做,所以将 \(a,b\) 从小到大排序
枚举 \(a_i\) ,每次把小于 \(a_i\) 的 \(b\) 加入优先队列,只要从中间选一个最大的匹配,之后将 \(-a_i\) 加入优先队列,表示可以反悔
代码真的短
# include <bits/stdc++.h>
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 <int> 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;
}
最新文章
- UOJ79 一般图最大匹配
- yii2分页的基本使用及其配置详解
- vue的transition过渡效果
- java文件编译及运行
- 手把手教你编写一个具有基本功能的shell(已开源)
- HTML控件-Select
- WPF实现渐变淡入淡出的动画效果
- NGINX(四)配置解析
- 简单实用 “易忘” 的SQL 语句语法,新老皆宜
- 使用ssh无密码登录
- 关于javascript面向对象之闭包
- delphi第2节
- rem 单位
- 『高性能模型』卷积复杂度以及Inception系列
- Flask-----Flask里引用哈希密码
- java中Scanner类nextInt之后用nextLine无法读取输入
- srtvlet filter
- 将Gridview中的数据出到excel或word中
- sql语句判断身份证性别等
- Android TabHost切换选项卡实现数据实时刷新
热门文章
- elasticsearch索引路径规则
- 【css】——三种方法实现多列等高
- Archlinux Setup AUR
- jdbc连接2(不可以注入)
- leetcode-166-分数到小数(用余数判断有没有出现小数的循环体)
- 删除Open with Atom右键菜单
- 【C#小知识】C#中一些易混淆概念总结(四)---------解析Console.WriteLine() 分类: C# 2014-02-05 17:18 1060人阅读 评论(0) 收藏
- Android 使用zxing生成二维码的方法
- 自己动手实现一个WEB服务器
- 机器学习--boosting家族之Adaboost算法