本文共 1593 字，大约阅读时间需要 5 分钟。

每个人做第一题需要$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 
   
    using namespace std;#define int long longconst int maxn = 1e6+10;struct edge{
   	int a,b,id;	bool operator < (const edge&tmp ) const{
    return a-b
    
     > 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] );}
    
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113625374 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！