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

$$\mathrm{YL杯超级篮球赛}$$

题目链接：

题目

一年一度的高一YL杯超级篮球赛开赛了。当然，所谓超级，意思是参赛人数可能多余 $5$ 人。小三对这项篮球非常感兴趣，所以一场都没有落下。每个中午都准时守侯在篮球场看比赛。经过一个星期的研究，小三终于对篮球的技战术找到了一丝丝感觉了。他发现打YL杯的每个班都有一套相似的进攻战术：

1. 控球后卫带球到前场，找到一个最佳攻击点 $(x,y)$
2. 所有除控卫以外的队员都从各自的当前位置迅速向 $(x,y)$ 移动
3. 控球后卫根据场上情况组织进攻

这个战术对于一般情况是非常奏效的，但是每个队员毕竟不像小三一样每天精力过剩，每个队员都有一个疲劳指数 $W$ ，显然对于每个队员的移动需要消耗一些能量。

假设一个队员从位置 $(x1,y1)$ 移动到 $(x,y)$ 的能量消耗为 $w\ast (ABS(x-x1)+ABS(y-y1))$ , 这里 $ABS$ 为绝对值函数。那么我们希望整个队伍一次进攻的能量消耗当然是越少越好。显然能量消耗的多少直接取决于控球后卫对于攻击点 $(x,y)$ 的选择。

因为参赛人数众多，所以小三希望你能编写一个程序，即帮他找出某个时刻的最佳攻击点。

输入

第一行：一个整数 $N$ ，表示篮球队人数

第二行：一共 $N$ 个整数，其中的第 $i$ 个数 $W_i$ 表示第i个队员的疲劳指数。

第 $3\sim N+2$行：每一行两个整数X和Y，其中的第 $i+2$ 行，表示第 $i$ 个队员的当前位置的横坐标和纵坐标。

输出

一个实数。表示所有队员集合到最佳攻击位置的能量消耗总和，答案保留两位小数。

样例输入

110 0

样例输出

0.00

数据范围

第一题 $N<=50000,x,y$ 都在longint范围内。

思路

这道题可以用贪心来做。

由题目得到 $x$ 轴其实和 $y$ 轴没有关系，我们只需要分别让所有的 $x_i-x1$ 的和与所有的 $y_i-y1$ 的和加起来分别最少。那我们就可以分开找到最佳攻击位置的 $x$ 轴坐标和 $y$ 轴坐标。

最后，我们只需要用过上面求队员能量消耗的公式，枚举每一个人，算出他的能量消耗。那么所有人能量消耗的总和就是答案了。

有一点要注意的是，因为 $x,y$ 都在longint范围内，所以要有关坐标的变量都要开long long。

代码

#include
   
    #include
    
     #define ll long longusing namespace std;struct node{   	int w;	ll x, y;}a[50001];int n, sum, now;ll ansx, ansy, ans;bool cmp1(node x, node y) {   //按x轴排序	return x.x < y.x;}bool cmp2(node x, node y) {   //按y轴排序	return x.y < y.y;}int main() {   	scanf("%d", &n);//读入	for (int i = 1; i <= n; i++) {   		scanf("%d", &a[i].w);//读入		sum += a[i].w;//所有人的疲劳值总和	}	for (int i = 1; i <= n; i++)		scanf("%lld %lld", &a[i].x, &a[i].y);//读入		sort(a + 1, a + n + 1, cmp1);//按x轴排序	for (int i = 1; i <= n; i++) {   //处理x轴		now += a[i].w;		if (now >= sum / 2 + 1) {   //疲劳值的和超过了一半			ansx = a[i].x;			break;		}	}		now = 0;//初始化	sort(a + 1, a + n + 1, cmp2);//按y轴排序	for (int i = 1; i <= n; i++) {   //处理y轴		now += a[i].w;		if (now >= sum / 2 + 1) {   //疲劳值的和超过了一半			ansy = a[i].y;			break;		}	}		for (int i = 1; i <= n; i++)		ans += (ll)a[i].w * (abs(ansx - a[i].x) + abs(ansy - a[i].y));//求出每一人的疲劳值		printf("%lld.00", ans);//输出		return 0;}