关注
笔试时写的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
相关推荐

点赞 评论 收藏
分享
牛客热帖
更多
正在热议
更多
# 你现在会用到哪些AI技能? #
6532次浏览 85人参与
# 蚂蚁求职进展汇总 #
123330次浏览 1163人参与
# 平安产险科技校招 #
854次浏览 0人参与
# 秋招踩过的“雷”,希望你别再踩 #
85738次浏览 1088人参与
# 我对___祛魅了 #
132500次浏览 736人参与
# 大厂VS公务员你怎么选 #
28206次浏览 397人参与
# 智慧芽求职进展汇总 #
1906次浏览 5人参与
# 你还有多少年退休? #
26948次浏览 192人参与
# 我的求职进度条 #
92218次浏览 1208人参与
# 实习在多还是在精 #
35323次浏览 243人参与
# 实习下班不想学习,正常吗? #
20466次浏览 174人参与
# 小马智行求职进展汇总 #
13757次浏览 50人参与
# 你的房租占工资的比例是多少? #
65031次浏览 800人参与
# 你见过哪些工贼行为 #
16942次浏览 91人参与
# 金蝶求职进展汇总 #
54102次浏览 263人参与
# 总结:哪家公司面试体验感最好 #
70369次浏览 416人参与
# 校招谈薪一定要知道的事 #
13639次浏览 118人参与
# 找工作中的小确幸 #
27603次浏览 282人参与
# 顺丰求职进展汇总 #
63610次浏览 314人参与
# 非技术岗投递进展 #
158139次浏览 1314人参与
# 反问环节如何提问 #
115603次浏览 2468人参与
# 你觉得材料多少算高薪 #
26315次浏览 159人参与