关注
笔试时写的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
相关推荐
俺不是程序猿ovo:扯毕设导师让回去做实验

点赞 评论 收藏
分享
05-25 10:45
门头沟学院 Java 点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 应届生,你找到工作了吗 #
1567次浏览 23人参与
# 双非应该如何逆袭? #
172278次浏览 2883人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
38031次浏览 275人参与
# 简历当中有水分算不算造假? #
3038次浏览 30人参与
# 谈薪时HR压价该怎么应对 #
205579次浏览 3177人参与
# 实习生的蛐蛐区 #
2553次浏览 33人参与
# 春招进度记录 #
340061次浏览 3162人参与
# 三一集团提前批进度交流 #
22004次浏览 138人参与
# 百度秋招提前批进度 #
104966次浏览 1121人参与
# 毕业旅行去哪玩儿 #
7651次浏览 121人参与
# 正在春招的你,也参与了去年秋招吗? #
308474次浏览 2523人参与
# 非技术岗投递进展 #
144236次浏览 1264人参与
# 双非有机会进大厂吗 #
433008次浏览 4325人参与
# 上班到公司第一件事做什么? #
60174次浏览 517人参与
# 百度工作体验 #
229321次浏览 2008人参与
# 秋招盘点:机械人值得去的企业 #
71832次浏览 670人参与
# 材料进Fab厂真的劝退吗? #
43005次浏览 184人参与
# 如果可以,你希望哪个公司来捞你 #
96426次浏览 397人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
115918次浏览 1133人参与
# 关于春招你都做了哪些准备? #
101696次浏览 666人参与
# 工作中,努力重要还是选择重要? #
139779次浏览 1703人参与