E. Train Hard, Win Easy(数学推导 + 前缀和)
Problem - E - Codeforces
这是一个有关竞赛编程的问题。Zibi 是一名竞赛编程教练，有 n 名选手想要备战。培训比赛具有一些不同寻常的规则——每个团队有两名成员和两个问题，每个选手都会编写其中一个问题的代码。当然，一个团队中的人将编写不同的问题。
评分规则也不是典型的。第一个问题总是一个实现问题：你必须非常快地实现某个众所周知的算法，而你的打字时间将被评分。第二个问题是一个可怕的几何任务，你只需要在合理的时间内得到它的通过。在这里，你的代码长度和难度很重要。之后，Zibi 将为每个方案给出一些罚分（可能是负数），团队的最终得分是它们的总和（得分越少，就越好）。
我们知道，当第 i 位选手编写第一个任务时，他总是会得到 xi 分，编写第二个任务时，他总是会得到 yi 分。我们可以假设，所有选手都知道彼此的技能，并在比赛期间分配问题，以最小化他们的最终得分。请记住，在比赛中，每个人都只编写一个问题。
Zibi 希望所有选手彼此之间进行比赛。然而，有 m 对人真的不喜欢合作，他们绝对不会在一起写比赛。尽管如此，教练将为所有可能的人组成团队，这些人不会互相厌恶。对于每个参与者，教练都感兴趣，他或她所训练的所有团队的得分总和是多少？
输入包含若干行：第一行包含两个整数 n 和 m（2≤n≤300000，0≤m≤300000）——参赛者数量和不想一起写比赛的人数。接下来的 n 行，每行包含两个整数 xi 和 yi（−109≤xi,yi≤109）——第 i 位选手在第一个问题和第二个问题上获得的分数。保证没有两个人既有 xi 又有 yi 相同的情况。最后的 m 行中，每行包含两个整数 ui 和 vi（1≤ui,vi≤n，ui≠vi）——不想在同一个团队中的人的索引。每个无序索引对最多出现一次。
输出 n 行，按照它们在输入中出现的顺序，输出所有参与者的得分总和。
Examples
input
Copy
3 2 1 2 2 3 1 3 1 2 2 3
output
Copy
3 0 3
input
Copy
3 3 1 2 2 3 1 3 1 2 2 3 1 3
output
Copy
0 0 0
input
Copy
5 3 -1 3 2 4 1 1 3 5 2 2 1 4 2 3 3 5
output
Copy
4 14 4 16 10
题解:
除了m种不会组队的,其他一定会组队,单个枚举的话n^2肯定会t,
那么我们可不可以先算出所有的贡献(假设没有之间不组队的人),所有人都相互组队
但这时又会有一个问题,我们如何确定组队时,谁写第一题谁写第二题?
假设我们设
a1 a2
b1 b2
如果a写第一题更优应该满足
a1 + b2 < b1 + a2
变形就成了
a1 - a2 < b1 - b2
我们按照这个排序一下,开始找最优
假设此时遍历到i,i的下标是id(原来的下标)
由于每一个人的顶多会和n - 1个人组队,
贡献其实就是统计前i - 1个人怎么选,(n - i)个人怎么选
由于我们排过序,前面i - 1个人,肯定选第一个比较好,(注意此时都是在和第i个比),前i-1的第二个由i选比较好
对于(n - i)个,排在i后面的,相比选(n - i)的第一个肯定不如选让i选第一个,那么(n - i)的都选第二个
当然对于不能组队的也要减去其贡献,每次记录id,代表其已经选过
然后看是否有和id不能一起组队的,
如果有又分为两种情况
1.被标记过,说明这个人在前面,说明当时肯定这个人选的是第一个,那么id选的就是第二个,减去贡献
2.刚好与第一种相反
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
#define int long long
typedef pair<int,int> PII;
int mod = 1e9 + 7;
int n,m;
struct node
{
int one,two,id;
}a[300050];
int one[300050];
int two[300050];
int last[300005];
vector<int> p[300050];
bool cmp(node a,node b)
{
return a.one - a.two < b.one - b.two;
}
int ans[300050];
void solve()
{
cin >> n >> m;
for(int i = 1;i <= n;i++)
{
cin >> a[i].one >> a[i].two;
a[i].id = i;
one[i] = a[i].one;
two[i] = a[i].two;
}
for(int i = 1;i <= m;i++)
{
int x,y;
cin >> x >> y;
p[x].push_back(y);
p[y].push_back(x);
}
sort(a + 1,a + 1 + n,cmp);
for(int i = n;i >= 1;i--)
last[i] = last[i + 1] + a[i].two;
map<int,int> f;
int pre = 0;
for(int i = 1;i <= n;i++)
{
int id = a[i].id;
f[id] = 1;
ans[id] += pre;
ans[id] += (i - 1)*a[i].two;
ans[id] += last[i + 1];
ans[id] += (n - i)*a[i].one;
for(int j = 0;j < p[id].size();j++)
{
int now = p[id][j];
if(f[now])
{
ans[id] -= one[now];
ans[id] -= two[id];
}
else
{
ans[id] -= one[id];
ans[id] -= two[now];
}
}
pre += a[i].one;
}
for(int i = 1;i <= n;i++)
cout << ans[i] <<" ";
}
signed main()
{
ios::sync_with_stdio(0 );
cin.tie(0);cout.tie(0);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
}