每日一题之过年

问题描述

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

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

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

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

输入格式

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

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

输出格式

输出一个整数表示答案。

#include <iostream>
#include<algorithm>
using namespace std;
int main()
{// 请在此输入您的代码int n;cin>>n;int a[n];for(int i=0;i<n;i++){cin>>a[i];}sort(a,a+n);cout<<(a[n-1]+a[0])/2;return 0;
}

其实这种题一般都是有规律，我看了这个题的标签是道思维题，所以自然而然的就去找规律，否则直接去模拟题意的话就会有点复杂。最小的猪一直在往正方向跑，坐标最大的猪一直在往负方向跑，取两数平均值即为答案。