前缀和+排序——cf1043E
2024-09-22 09:11:59
先不考虑第二个条件
要求i和所有其他人的分数和最小,选择x还是y,可以推出一个公式,即差xi-yi小的j都选y,反之都选x
那么按照xi-yi排序即可
然后再考虑第二个条件,做减法就行
/*
xi+yj<xj+yi
xi-yi<xj-yj
xi-yi值小取xi
xi-yi值大取yi
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 300005
struct Node {
ll x,y,id;
}p[N],q[N];
int n,m;
ll ans[N],sumx[N],sumy[N];
int cmp(Node a,Node b){return a.x-a.y<b.x-b.y;}
int main(){
cin>>n>>m;
for(int i=;i<=n;i++)
scanf("%lld%lld",&p[i].x,&p[i].y),p[i].id=i;
for(int i=;i<=n;i++)q[i]=p[i]; sort(p+,p++n,cmp);
for(int i=;i<=n;i++){
sumx[i]=sumx[i-]+p[i].x;
sumy[i]=sumy[i-]+p[i].y;
}
for(int i=;i<=n;i++){
ans[p[i].id]+=(i-)*p[i].y;
ans[p[i].id]+=sumx[i-];
ans[p[i].id]+=(n-i)*p[i].x;
ans[p[i].id]+=sumy[n]-sumy[i];
} while(m--){
int u,v;
scanf("%d%d",&u,&v);
Node a=q[u],b=q[v];
ll sum=min(a.x+b.y,a.y+b.x);
ans[u]-=sum;
ans[v]-=sum;
}
for(int i=;i<=n;i++)
cout<<ans[i]<<" ";
}
最新文章
- 小议jQuery插件开发
- 关于AJAX中status中12030与12031的错误
- iOS做新浪微博sso授权登录遇到的一些坑
- HorizontalScrollView的配置
- AngularJS 实现的输入自动完成补充功能
- Python深入05 装饰器
- centos 安装git 服务端
- Linux驱动开发cdev驱动分层设计
- openwrt interface
- ORACLE主要的系统表和系统视图
- RMAN完整全备份
- HDU 4070 Phage War
- URL vs. HTML 录制模式
- poj 2513 连接火柴 字典树+欧拉通路 好题
- Spring + Mybatis 项目实现动态切换数据源
- Linux实战教学笔记11:linux定时任务
- [SDOI2011]染色 线段树+树链剖分
- Java jar包启动脚本
- mac os High Sierra 升级错误
- 如何实现圆形的进度条(ProgressBar)