关注
笔试时写的O(n2),过70%,笔试后想到的O(nlongn),(这里假设冲突对不会重复)
#include<iostream>
(5488)#include<algorithm>
#include<vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(n);
vector<int> del(n);
int sup = 0;
for (int i = 0; i < n; ++i) {
cin >> a[i] >> b[i];
sup += b[i];
del[i] = b[i] - a[i];
}
vector<int> ans(n, sup);
for (int i = 0; i < n; ++i)
ans[i] += n * b[i];
sort(del.begin(), del.end());
vector<int> sum(n + 1, 0);
for (int i = 0; i < n; ++i)
sum[i + 1] = sum[i] + del[i];
for (int i = 0; i < n; ++i) {
int curDel = b[i] - a[i];
int idx = upper_bound(del.begin(), del.end(), curDel)- del.begin();
ans[i] -= sum[n] - sum[idx];
ans[i] -= idx * curDel;
ans[i] -= b[i] + a[i];
}
for (int i = 0; i < m; ++i) {
int l, r;
cin >> l >> r;
--l; --r;
int curDel = min(a[l] + b[r], a[r] + b[l]);
ans[l] -= curDel;
ans[r] -= curDel;
}
for (int i = 0; i < n; ++i)
cout << ans[i] << " ";
return 0;
}
查看原帖
1 3
相关推荐
点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 秋招什么时候开投比较合适? #
23732次浏览 318人参与
# 百度工作体验 #
223429次浏览 1973人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
27982次浏览 216人参与
# 机械人与华为的爱恨情仇 #
117159次浏览 946人参与
# 发工资后,你做的第一件事是什么 #
68161次浏览 229人参与
# 机械人集合!你是什么工程师? #
15818次浏览 89人参与
# 你觉得实习能学到东西吗 #
36329次浏览 712人参与
# 找不到好工作选择GAP真的丢人吗 #
78275次浏览 938人参与
# 我想去国央企的原因 #
59999次浏览 393人参与
# 如何准备秋招 #
20683次浏览 390人参与
# 工作中哪个瞬间让你想离职 #
25916次浏览 177人参与
# 入职第四天,心情怎么样 #
29454次浏览 417人参与
# 拼多多工作体验 #
28545次浏览 197人参与
# 多益网络求职进展汇总 #
29234次浏览 134人参与
# 快手求职进展汇总 #
547111次浏览 6001人参与
# 硬件应届生薪资是否普遍偏低? #
74102次浏览 514人参与
# 不考虑转正,实习多久合适 #
32331次浏览 145人参与
# 面试中,你被问过哪些奇葩问题? #
68560次浏览 796人参与
# 你们公司几号发工资 #
21236次浏览 140人参与
# 如果再来一次,你还会学硬件吗 #
125794次浏览 1402人参与
# 实习,不懂就问 #
46399次浏览 693人参与