洛谷 P1889 士兵站队
2024-08-27 23:54:17
题目描述
在一个划分成网格的操场上, n个士兵散乱地站在网格点上。由整数 坐标 (x,y) 表示。士兵们可以沿网格边上、下左右移动一步,但在同时刻任一网格点上只能有名士兵。按照军官的命令,们要整齐地列成个水平队列,即排成 队列,即排成 (x,y),(x+1,y), …,(x+n -1,y) 。如何选择 x 和y的值才能使 士兵们以最少的总移动步数排成一列。
输入输出格式
输入格式:
文件的第 1 行是士兵数 n,1≤n≤10000 。接下来 n 行是士兵的初始位置, 每行 2 个整数 x 和y,-10000 ≤x,y≤10000 。
输出格式:
文件中 只有一个整 数是士兵排成一行需要的最少移动步。
输入输出样例
输入样例#1: 复制
5
1 2
2 2
1 3
3 -2
3 3
输出样例#1: 复制
8
思路:小学奥数。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans;
int midx,midy;
int x[],y[];
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
sort(x+,x++n);
sort(y+,y++n);
for(int i=;i<=n;i++) x[i]-=i;
sort(x+,x++n);
if(n%==){ midx=x[n/2+1];midy=y[n/2+1]; }
else{ midx=(x[n/]+x[n/+]+)/;midy=(y[n/]+y[n/+]+)/; }
for(int i=;i<=n;i++)
ans+=abs(midx-x[i])+abs(midy-y[i]);
cout<<ans;
}
最新文章
- [数据科学] 从csv, xls文件中提取数据
- 偷懒小工具 - Excel导出公共类
- error C4430: missing type specifier - int assumed. Note: C++ does not support default-int
- 黄聪:CamtasiaStudio如何导出视频上传优酷实现高清
- Android 视频播放器切换到下个视频时残留上个视频画面的解决办法
- microstrip(微带线)、stripline(带状线) 指什么?
- IOS网络开发(二)
- SQL里面如何取得前N条数据?
- iOS开发 在scrollView上增加滑动手势(Pan)
- 不同浏览器下的CSS HACK
- BZOJ 1812: [Ioi2005]riv( 树形dp )
- beini破解无线
- 老男孩Python视频教程:第一周
- [POJ 3487]The Stable Marriage Problem
- 【JavaScript】封装实用方法【持续积累】
- [UWP]为什么ContentControl的ControlTemplate里放两个ContentPresenter会出问题(绕口)
- Linux分区知识及企业场景分区76
- [Unity动画]04.Avatar Mask
- JavaScript进行简单的随即验证码生成(适合和我一样刚入门一本完整的教材书都没看完的弟弟)
- Linux ->;>; UBuntu 14.04 LTE下主机名称和IP地址解析