第 25 场 蓝桥月赛

3.过年【算法赛】 - 蓝桥云课

问题描述

蓝桥村的村民们正准备迎接新年。他们计划宰杀 N 头猪，以庆祝一整年的辛勤劳作和丰收。每头猪的初始位置位于下标 xi​，所有 xi​ 均为偶数，保证没有两头猪初始位置相同。

当猪意识到人类打算宰杀它们时，并非束手就擒。它们会主动移动以寻找同伴，遵循以下规则：

• 每头猪以恒定速率朝着最近的另一头猪移动。若有多头猪距离相同，则选择朝着坐标更小的猪移动。所有猪的移动速度相同。
• 当两只猪相遇在同一坐标时，它们会融合成一个整体，被视为一头猪。

当所有猪聚集在同一坐标点时停止移动。现在村民们想要确定最终猪群聚集的确切坐标位置，请你帮助解决这个问题。

输入格式

第一行输入一个整数 N（2≤N≤105）表示猪的数量。

第二行输入 N 个整数 x1​,x2​,⋯,xN​（−109≤xi​≤109）表示每头猪的坐标，保证 x1​,x2​,⋯,xN​ 是偶数，且各不相同。

输出格式

输出一个整数表示答案。

样例输入

5
0 -2 4 10 2

样例输出

8

思路：

1. 中位数性质：由于所有猪都以恒定速率向最近的猪移动，最终它们会聚集在初始位置的中位数上。这是因为中位数位置是所有位置中距离其他位置总和最小的点。

2. 排序：由于我们只需要找到中位数，我们可以先对猪的初始位置进行排序，然后直接选择排序后数组的中间元素作为最终聚集点。

3. 方向：最右边的猪会往左，最左边的猪会往右，通常要画一个样例

代码：

#include <iostream>
#include<algorithm>
#include<cmath> 
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
ll n;
ll arr[N];
int main() 
{cin >> n;for(ll i = 1 ; i <= n ; i++)cin >> arr[i];sort(arr+1,arr+1+n);int mid = (abs(arr[1]) + abs(arr[n])) / 2;cout << arr[n] - mid;return 0;
}