题号 NC113104
名称 Train Hard, Win Easy
来源 CF1043E
戳我进入往期每日一题汇总贴~
往期每日一题二期题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情
欢迎给每日一题投稿，投稿需要提供牛客题库里的题目+题解 投稿有牛币奖励，可发站内信给王清楚或联系QQ 234186389
每日一题QQ群:659028468

题解

作者 喵渺淼妙的死忠粉
题意:
=
题意有点难懂,这里解释一下.
题意:给你n组数,每组都可以和其他组配对,然后你只能选这个组的a类,那个组的b类/这个组的b类,那个组的a类.然后要求总和最小,当然还给了m组不能配对的点,然后输出每组配对所获得的值.

思路:

暴力的思路十分简单,就是一一配对,然后一一比较即可.但是这样做的时间复杂度是的,显然是不可行的.
那么我们优化思路,发现每次配对都是选a/b,且选出来最优,那么我们直接sort一下,把选a点更优的点放前面,然后就完成了(因为具有单调性.)然后-那些不能选的点的贡献即可.这样的时间复杂度就是.这里用前缀和记录下a的前缀,后缀和记录下b的后缀即可.

代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+5;
struct solve{
    ll a,b,id;
}w[N];
int pos[N];//查询原来的id现在的位子.
bool cmp(solve A,solve B)
{
    return A.a+B.b<B.a+A.b;
}
ll ans[N],pre[N],suf[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&w[i].a,&w[i].b);
        w[i].id=i;
    }sort(w+1,w+1+n,cmp);
    for(int i=1;i<=n;i++)    pos[w[i].id]=i,pre[i]+=pre[i-1]+w[i].a;
    for(int i=n;i>=1;i--)    suf[i]+=suf[i+1]+w[i].b;
    for(int i=1;i<=n;i++)    ans[w[i].id]=pre[i-1]+1ll*(i-1)*w[i].b+suf[i+1]+1ll*(n-i)*w[i].a;
    for(int i=1;i<=m;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        if(pos[u]<pos[v])    ans[u]-=(w[pos[u]].a+w[pos[v]].b),ans[v]-=(w[pos[u]].a+w[pos[v]].b);
        else                ans[u]-=(w[pos[u]].b+w[pos[v]].a),ans[v]-=(w[pos[u]].b+w[pos[v]].a);
    }
    for(int i=1;i<=n;i++)    printf("%lld ",ans[i]);
    puts("");
    return 0;
}

欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目2月20日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴