关注
所以代码只通过了例子,不保证代码能ac #include <iostream>
#include <cmath>
using namespace std;
int dis(int mid_x, int mid_y, int x[], int y[],int start,int end) {
int step = 0;
for (int i=start;i<end;i++){
step += abs(mid_x - x[i]) + abs(mid_y - y[i]);
}
return step;
};
int get_step(int x[], int y[],int start,int end){
int min_x = 1000;
int max_x = 0;
int min_y = 1000;
int max_y = 0;
for (int i=start;i<end;i++){
max_x = max(x[i],max_x);
min_x = min(x[i],min_x);
max_y = max(y[i],max_y);
min_y = min(y[i],min_y);
}
int mid_x = (min_x + max_x)/2;
int mid_y = (min_y + max_y)/2;
int last_mid_x = mid_x+1;
int last_mid_y = mid_y+1;
int min_step=10000;
while(max_x-min_x>=1){
while (max_y-min_y>=1){
if (dis(mid_x,mid_y,x,y,start,end)>dis(mid_x,max_y,x,y,start,end)){
min_y = mid_y;
}else{
max_y = mid_y;
}
min_step = min(dis(mid_x,mid_y,x,y,start,end),dis(mid_x,max_y,x,y,start,end));
last_mid_y = mid_y;
if (last_mid_y==(min_y + max_y)/2){
break;
}
mid_y = (min_y + max_y)/2;
};
if(dis(mid_x,mid_y,x,y,start,end) > dis(max_x,mid_y,x,y,start,end))
min_x = mid_x;
else
max_x = mid_x;
min_step = min(dis(mid_x,mid_y,x,y,start,end) , dis(max_x,mid_y,x,y,start,end));
last_mid_x = mid_x;
if (last_mid_x==(min_x + max_x)/2){
break;
}
mid_x = (min_x + max_x)/2;
}
return min_step;
}
void get_steps(int x[], int y[],int n) {
cout<<0<<' ';
for (int i=2;i<n;i++){
int min_step = 1000;
for(int j=0;j<n-i;j++){
min_step = min(min_step,get_step(x,y,j,j+i));
}
cout<<min_step<<' ';
}
cout<<get_step(x,y,0,n)<<endl;
};
int main() {
int n;
cin >> n;
int x[n], y[n];
for (int j = 0; j < n; j++) {
cin >> x[j];
}
for (int j = 0; j < n; j++) {
cin >> y[j];
}
get_steps(x,y,n);
return 0;
}
查看原帖
点赞 7
相关推荐
06-08 23:32
北京工业大学 C++ 点赞 评论 收藏
分享
点赞 评论 收藏
分享
06-15 01:01
中南大学 嵌入式硬件工程师 点赞 评论 收藏
分享
牛客热帖
更多
- 1... 🌟择难路,未有疑,四非学院本运气拉满,春招拿下大厂后端6.1W
- 2... 秋招应该侧重准备哪个部分的内容1.0W
- 3... 腾讯云智后台开发暑期面经8440
- 4... 史上最细SQL实战系列:sql笔试例题总结篇(建议收藏)8152
- 5... 25届毕业现在在家呆了一个多月,没工作8152
- 6... 恋爱四年没想到过自己会出轨7992
- 7... 其实主包早就找到工作了,但还是每天都刷6303
- 8... 字节实习week6:听leader吐槽当前的应届生候选人们4908
- 9... 离开软件测试才发现外面没有雨4655
- 10... 作为实习生,我问薪无愧4631
正在热议
更多
# 应届生,你找到工作了吗 #
2117次浏览 31人参与
# 双非应该如何逆袭? #
173179次浏览 2937人参与
# 现代汽车前瞻技术研发急速编程挑战赛 #
38588次浏览 278人参与
# 简历当中有水分算不算造假? #
4023次浏览 40人参与
# 春招进度记录 #
340831次浏览 3212人参与
# 实习生的蛐蛐区 #
3456次浏览 35人参与
# 谈薪时HR压价该怎么应对 #
205749次浏览 3177人参与
# 百度秋招提前批进度 #
105123次浏览 1123人参与
# 三一集团提前批进度交流 #
22166次浏览 138人参与
# 毕业旅行去哪玩儿 #
7833次浏览 123人参与
# 双非有机会进大厂吗 #
433880次浏览 4373人参与
# 正在春招的你,也参与了去年秋招吗? #
308652次浏览 2523人参与
# 非技术岗投递进展 #
144403次浏览 1264人参与
# 百度求职进展汇总 #
406241次浏览 4718人参与
# 上班到公司第一件事做什么? #
60405次浏览 521人参与
# 秋招盘点:机械人值得去的企业 #
71934次浏览 670人参与
# 材料进Fab厂真的劝退吗? #
43134次浏览 184人参与
# 我的OC时间线 #
814622次浏览 7746人参与
# 百度工作体验 #
229660次浏览 2010人参与
# 没有合适的工作,你会先找个干着,还是考公考研 #
116070次浏览 1133人参与
# 如果可以,你希望哪个公司来捞你 #
96607次浏览 397人参与