笔试时写的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

相关推荐

07-02 10:44
门头沟学院 C++
码农索隆:太实诚了,告诉hr,你能实习至少6个月
点赞 评论 收藏
分享
05-25 10:45
门头沟学院 Java
Frank_zhan...:没实习一个项目肯定不够,可以再做一个轮子,技术栈再补一个mq,微服务,整体再换个简历模板,暑期尽量再找一个日常实习
无实习如何秋招上岸
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-01 11:27
点赞 评论 收藏
分享
牛客网
牛客网在线编程
牛客网题解
牛客企业服务