蓝桥杯 过年【算法赛】
问题形貌蓝桥村的村民们正准备迎接新年。他们计划宰杀 NN 头猪，以庆贺一整年的辛勤劳作和丰收。每头猪的初始位置位于下标 xixi，所有 xixi 均为偶数，包管没有两头猪初始位置相同。
当猪意识到人类计划宰杀它们时，并非束手就擒。它们会自动移动以探求搭档，遵循以下规则：
[*]每头猪以恒定速率朝着最近的另一头猪移动。如有多头猪距离相同，则选择朝着坐标更小的猪移动。所有猪的移动速度相同。
[*]当两只猪相遇在同一坐标时，它们会融合成一个团体，被视为一头猪。
当所有猪聚集在同一坐标点时停止移动。现在村民们想要确定终极猪群聚集简直切坐标位置，请你资助办理这个问题。
输入格式
第一行输入一个整数 N(2≤N≤105)N(2≤N≤105) 表示猪的数量。
第二行输入 NN 个整数 x1,x2,⋯ ,xN(−109≤xi≤109)x1,x2,⋯,xN(−109≤xi≤109) 表示每头猪的坐标，包管 x1,x2,⋯xNx1,x2,⋯xN 是偶数，且各不相同。
输出格式
输出一个整数表示答案。
样例输入
5
0 -2 -4 10 2
https://i-blog.csdnimg.cn/direct/a1485eeeff124c2c9fca4d8739fab81a.png
样例输出
3有点蠢，我自己模拟了一次运动过程，不过练习了链表，全部超时
#include <iostream>
#include <algorithm>
#include <list>
#include <cmath>
#include <climits>
using namespace std;
int main()
{
int n;
cin>>n;
double nums;
for(int i=0; i<n; i++){
cin>>nums;
}
sort(nums, nums+n);
list<double> nums_l;
for(int i=0; i<n; i++){
nums_l.push_back(nums);
}
// for(list<int>::iterator i=nums_l.begin(); i != nums_l.end(); i++){
// cout<<*i<<" ";
// }
// cout<<endl;
int cur_n = n;
while(1){
double min_step = INT_MAX;
for(list<double>::iterator i=nums_l.begin(); i != nums_l.end(); i++){
double step;
if(i == nums_l.begin()){
continue;
}
else{
list<double>::iterator pre_iter = i;
list<double>::iterator next_iter = i;
--pre_iter;
++next_iter;
if(next_iter == nums_l.end()){
step = (*i - *pre_iter) / 2;
}
else{
step = min(*i - *pre_iter, *next_iter - *i) / 2;
}
min_step = step < min_step ? step : min_step;
}
}
// cout<<"min_step: "<<min_step<<endl;
double delay_step, cur_step;
for(list<double>::iterator i=nums_l.begin(); i != nums_l.end(); i++){
if(i == nums_l.begin()){
delay_step = min_step;
continue;
}
list<double>::iterator pre_iter = i;
list<double>::iterator next_iter = i;
--pre_iter;
++next_iter;
if(next_iter == nums_l.end()){
*i -= min_step;
}
else{
if(*i - *pre_iter <= *next_iter - *i){
cur_step = -min_step;
}
else{
cur_step = min_step;
}
}
*pre_iter += delay_step;
delay_step = cur_step;
}
// cout<<"Moving!"<<endl;
// for(list<int>::iterator i=nums_l.begin(); i != nums_l.end(); i++){
// cout<<*i<<" ";
// }
// cout<<endl;
list<double>::iterator cur_it=nums_l.begin();
while(cur_it != nums_l.end()){
if(cur_it == nums_l.begin()){
++cur_it;
continue;
}
list<double>::iterator pre_iter = cur_it;
--pre_iter;
if(*pre_iter == *cur_it){
cur_it = nums_l.erase(cur_it);
}
else{
++cur_it;
}
}
if(nums_l.size() == 1){
break;
}
// cout<<"Merging!"<<endl;
// for(list<int>::iterator i=nums_l.begin(); i != nums_l.end(); i++){
// cout<<*i<<" ";
// }
// cout<<endl;
}
cout<<*nums_l.begin();
return 0;
}
实在求中点就好了,从数据范围应该要看得出来模拟肯定超时
#include <iostream>
#include <algorithm>
#include <list>
#include <cmath>
#include <climits>
using namespace std;
int main()
{
int n;
cin>>n;
double nums;
for(int i=0; i<n; i++){
cin>>nums;
}
sort(nums, nums+n);
cout<<(nums+nums)/2;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]