GESP C++ 七级真题解析：金币收集

题目描述

小 A 正在游玩收集金币的游戏。具体来说，在数轴上将会出现 n 枚金币，其中第 i 枚金币位于坐标 x_i 处。你需要从原点出发，收集所有的金币，求所需的最小移动距离。

输入格式

第一行包含一个整数 n，表示金币的数量。 第二行包含 n 个整数，表示每枚金币的坐标 x_i。

输出格式

输出一个整数，表示收集所有金币所需的最小移动距离。

数据范围

对于 100% 的数据，1 <= n <= 10^5，-10^9 <= x_i <= 10^9。

解题思路

这是一个典型的贪心算法问题。由于金币分布在数轴上，我们需要考虑正半轴和负半轴的金币。

1. 排序：首先将所有金币的坐标进行排序。
2. 分类：将金币分为负数坐标（左侧）和正数坐标（右侧）。
3. 策略：
   • 如果只有一侧有金币，直接走到最远端即可。
   • 如果两侧都有金币，有两种最优路径：
     • 先向左走到最左边的金币，再向右走到最右边的金币。
     • 先向右走到最右边的金币，再向左走到最左边的金币。
   • 最小距离为上述两种方案中的较小值。

具体公式为：min(2 * |left_min| + right_max, 2 * right_max + |left_min|)，其中 left_min 是最小的负坐标，right_max 是最大的正坐标。

参考代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;

    vector<int> coins(n);
    for (int i = 0; i < n; ++i) {
        cin >> coins[i];
    }

    sort(coins.begin(), coins.end());

    
     left_pos = coins[];
     right_pos = coins[n - ];

      dist = ;

     (left_pos >= ) {
        
        dist = right_pos;
    }   (right_pos <= ) {
        
        dist = (left_pos);
    }  {
        
          option1 =  * (left_pos) + right_pos;
          option2 =  * right_pos + (left_pos);
        dist = (option1, option2);
    }

    cout << dist << endl;

     ;
}