Codeforces 709B Checkpoints ( 模拟)

53 阅读 0 评论 35 点赞

我是靠谱客的博主称心绿茶，最近开发中收集的这篇文章主要介绍Codeforces 709B Checkpoints ( 模拟)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

http://codeforces.com/problemset/problem/709/B

B. Checkpoints

Vasya takes part in the orienteering competition. There are n checkpoints located along the line at coordinates x1, x2, …, xn. Vasya starts at the point with coordinate a. His goal is to visit at least n - 1 checkpoint in order to finish the competition. Participant are allowed to visit checkpoints in arbitrary order.

Vasya wants to pick such checkpoints and the order of visiting them that the total distance travelled is minimized. He asks you to calculate this minimum possible value.

Input
The first line of the input contains two integers n and a (1 ≤ n ≤ 100 000, - 1 000 000 ≤ a ≤ 1 000 000) — the number of checkpoints and Vasya’s starting position respectively.

The second line contains n integers x1, x2, …, xn ( - 1 000 000 ≤ xi ≤ 1 000 000) — coordinates of the checkpoints.

Output
Print one integer — the minimum distance Vasya has to travel in order to visit at least n - 1 checkpoint.

Examples
input
3 10
1 7 12
output
7
input
2 0
11 -10
output
10
input
5 0
0 0 1000 0 0
output
0

题意：坐标上有n个棋子，然后固定了初始位置。为了获得至少n-1个棋子，所需要走的最少的路程。

大模拟： 现在已经丧失了模拟的能力。这个处理的时候有些技巧，不然模拟的会很麻烦。虽然一个位置上可能有多个棋子，但是把每个棋子当做不同的位置来看会处理的更方便。然后计算距离的时候，先计算最远的两个间的距离再加上初始与两个距离的最小值。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <math.h>
using namespace std;

const int N = 1e5 + 100;
int arr[N];
int main()
{
    int n,a;
    scanf("%d%d",&n,&a);
    for(int i=0;i<n;i++)  scanf("%d",&arr[i]);
    sort(arr,arr+n);
    if (n==1) {
        cout << 0 << endl;
        return 0;
    }
    int ans1,ans2;
    int tmp1=arr[1], tmp2=arr[n-1];
    ans1 = tmp2-tmp1+min(abs(tmp1-a),abs(tmp2-a));

    tmp1=arr[0], tmp2=arr[n-2];
    ans2 = tmp2-tmp1+min(abs(tmp1-a),abs(tmp2-a));

    cout << min(ans1,ans2) << endl;
    return 0;
}