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

传送门

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

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

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

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

考虑和

花费是

两种选择方式的费用差是

也就是

当说明的方式比较好(因为差是正数)

当说明的方式比较好(因为差是负数)

那我们按照来排个序

对于第个人来说

个人由于比较小,所以都是贡献出来

个人由于比较大,所以都是贡献说来

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

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

#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] );
}