1043 E. Train Hard, Win Easy(贪心.)

传送门

每个人做第一题需要 $a_i$ 事件,做第二题需要 $b_i$ 的事件

每个人都要和其他 $n-1$ 个人组成一组队伍做一次题,你能选择的就是谁做第一题谁做第二题。

但是现在有 $m$ 对关系起了冲突,不能组队

求能组队的最小花费时间总和.

$n<=300000$

考虑 $(a_i,b_i)$ 和 $(a_j,b_j)$

花费是 $min(a_i+b_j,b_i+a_j)$

两种选择方式的费用差是 $a_i+b_j-a_j-b_i$

也就是 $(a_i-b_i)-(a_j-b_j)$

当 $a_i-b_i>a_j-b_j$ 说明 $b_i+a_j$ 的方式比较好(因为差是正数)

当 $a_i-b_i<a_j-b_j$ 说明 $a_i+b_j$ 的方式比较好(因为差是负数)

那我们按照 $a_i-b_i$ 来排个序

对于第 $i$ 个人来说

$[1,i-1]$ 个人由于 $a_j-b_j$ 比较小,所以都是贡献 $a_j$ 出来

$[i+1,n]$ 个人由于 $a_j-b_j$ 比较大,所以都是贡献 $b_j$ 说来

如此一来,计算一个 $a,b$ 数值的前缀和就可以轻松求解

至于 $m$ 对关系,直接暴力减去就好了。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6+10;
struct edge{
    int a,b,id;
    bool operator < (const edge&tmp ) const{ return a-b<tmp.a-tmp.b;}
}s[maxn];
int ans[maxn],n,m,prea[maxn],preb[maxn];
signed main()
{
    cin >> n >> m;
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld",&s[i].a,&s[i].b );
        s[i].id = i;
    }
    for(int i=1;i<=m;i++)
    {
        int l,r; scanf("%lld%lld",&l,&r);
        ans[l] -= min(s[l].a+s[r].b,s[l].b+s[r].a);
        ans[r] -= min(s[l].a+s[r].b,s[l].b+s[r].a);
    }
    sort( s+1,s+1+n );
    for(int i=1;i<=n;i++)
    {
        prea[i] = prea[i-1]+s[i].a;
        preb[i] = preb[i-1]+s[i].b;
    }
    for(int i=1;i<=n;i++)
    {
        int x = prea[i-1],y = preb[n]-preb[i];
        ans[s[i].id] += x+y+(i-1)*s[i].b+(n-i)*s[i].a;    
    }
    for(int i=1;i<=n;i++)
        printf("%lld ",ans[i] );
}