网站程序上传教程,wordpress文章显示404,丹阳房产网,网站外链发布平台3.过年【算法赛】 - 蓝桥云课
问题描述
蓝桥村的村民们正准备迎接新年。他们计划宰杀 N 头猪#xff0c;以庆祝一整年的辛勤劳作和丰收。每头猪的初始位置位于下标 xi#xff0c;所有 xi 均为偶数#xff0c;保证没有两头猪初始位置相同。
当猪意识到人类打算宰杀它们…3.过年【算法赛】 - 蓝桥云课
问题描述
蓝桥村的村民们正准备迎接新年。他们计划宰杀 N 头猪以庆祝一整年的辛勤劳作和丰收。每头猪的初始位置位于下标 xi所有 xi 均为偶数保证没有两头猪初始位置相同。
当猪意识到人类打算宰杀它们时并非束手就擒。它们会主动移动以寻找同伴遵循以下规则
每头猪以恒定速率朝着最近的另一头猪移动。若有多头猪距离相同则选择朝着坐标更小的猪移动。所有猪的移动速度相同。当两只猪相遇在同一坐标时它们会融合成一个整体被视为一头猪。
当所有猪聚集在同一坐标点时停止移动。现在村民们想要确定最终猪群聚集的确切坐标位置请你帮助解决这个问题。
输入格式
第一行输入一个整数 N2≤N≤105表示猪的数量。
第二行输入 N 个整数 x1,x2,⋯,xN−109≤xi≤109表示每头猪的坐标保证 x1,x2,⋯,xN 是偶数且各不相同。
输出格式
输出一个整数表示答案。
样例输入
5
0 -2 4 10 2
样例输出
8
思路 中位数性质由于所有猪都以恒定速率向最近的猪移动最终它们会聚集在初始位置的中位数上。这是因为中位数位置是所有位置中距离其他位置总和最小的点。 排序由于我们只需要找到中位数我们可以先对猪的初始位置进行排序然后直接选择排序后数组的中间元素作为最终聚集点。 方向最右边的猪会往左最左边的猪会往右通常要画一个样例
代码
#include iostream
#includealgorithm
#includecmath
using namespace std;
typedef long long ll;
const ll N 1e510;
ll n;
ll arr[N];
int main()
{cin n;for(ll i 1 ; i n ; i)cin arr[i];sort(arr1,arr1n);int mid (abs(arr[1]) abs(arr[n])) / 2;cout arr[n] - mid;return 0;
}
