hdoj 2083 简易版之最短距离
2024-09-16 05:59:12
简易版之最短距离
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 13510 Accepted Submission(s):
6000
Problem Description
寒假的时候,ACBOY要去拜访很多朋友,恰巧他所有朋友的家都处在坐标平面的X轴上。ACBOY可以任意选择一个朋友的家开始访问,但是每次访问后他都必须回到出发点,然后才能去访问下一个朋友。
比如有4个朋友,对应的X轴坐标分别为1,
2, 3, 4。当ACBOY选择坐标为2的点做为出发点时,则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| =
4。
现在给出N个朋友的坐标,那么ACBOY应该怎么走才会花费时间最少呢?
比如有4个朋友,对应的X轴坐标分别为1,
2, 3, 4。当ACBOY选择坐标为2的点做为出发点时,则他最终需要的时间为 |1-2|+|2-2|+|3-2|+|4-2| =
4。
现在给出N个朋友的坐标,那么ACBOY应该怎么走才会花费时间最少呢?
Input
输入首先是一个正整数M,表示M个测试实例。每个实例的输入有2行,首先是一个正整数N(N <=
500),表示有N个朋友,下一行是N个正整数,表示具体的坐标(所有数据均<=10000).
500),表示有N个朋友,下一行是N个正整数,表示具体的坐标(所有数据均<=10000).
Output
对于每一个测试实例,请输出访问完所有朋友所花的最少时间,每个实例的输出占一行。
Sample Input
2
2
2 4
3
2 4 6
Sample Output
2
4
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
bool cmp(int a,int b)
{
return a<b;
}
int main()
{
int n,m,j,i,s,t,sum;
int a[1100];
scanf("%d",&n);
while(n--)
{
scanf("%d",&m);
sum=0;s=0;
for(i=0;i<m;i++)
scanf("%d",&a[i]);
sort(a,a+m,cmp);
if(m%2!=0)
{
s=(m-1)/2;
for(i=0;i<m;i++)
{
sum+=abs(a[i]-a[s]);
}
}
else
{
s=m/2-1;
for(i=0;i<m;i++)
{
sum+=abs(a[i]-a[s]);
}
}
printf("%d\n",sum);
sum=0;
}
return 0;
}
最新文章
- H5单页面手势滑屏切换原理
- springMVC的配置文件路径问题
- [Asp.net 5] Configuration-新一代的配置文件(ConfigurationSource的多种实现)
- MVC中return File(byte[],";image/jpeg";)输入图片不清晰
- iis7.5错误 配置错误
- Google搜索命令语法大全
- 【锋利的JQuery-学习笔记】广告栏
- Unity中的各种寻找GameObject方法
- poj3070--Fibonacci(矩阵的高速幂)
- MySQL动态添删改列字段
- 一:配置使用阿里云Maven库
- Spring Security 入门(1-1)Spring Security是什么?
- vue-cli2.9.1如何自动打开浏览器及实现手机调试
- MySQL复制框架
- ELK之elasticsearch6安装认证模块search guard
- angular组件之间的通讯
- MFC连接MySQL数据库方法
- C# Azure 用Webhook添加警报规则
- bootstrap模态框input不能获取焦点并编辑【转】
- [转载]TypeScript 入门指南
热门文章
- VMware linux与windows文件共享
- http://jingyan.baidu.com/article/a3761b2b66fe141577f9aa51.html
- Android Spinner(级联 天气预报)
- Ubuntu 12.04安装字体
- Nginx 实现MySQL的负载均衡
- 面试大总结之二:Java搞定面试中的二叉树题目
- HDU1054Strategic Game(最小顶点覆盖数)
- python学习笔记七--数据操作符
- SPOJ 962 Intergalactic Map (从A到B再到C的路线)
- 使用VS2010调用matlab的mat格式文件