C++蜗蜗是个园丁望快

Question

蜗蜗是个园丁
描述
提交
自定义测试
蜗蜗是蜗蜗国最厉害的园丁，每天负责给蜗蜗国的中央大道上的植物浇水。已知中央大道是一条直线，上面有 n 棵位置互不相同的植物，它们的位置分别为 a1,a2,…,an 。蜗蜗每天需要从位置 0 开始，把每棵植物都浇一遍水，但他有点懒，希望能够走最少的路程，浇完所有的植物，请你让他。

已知从位置 i 到位置 j（i<j)，需要走的路程为 j−i。蜗蜗在走路的时候不会停，只有在给植物浇水的时候会停下来。每浇完一棵植物（或者从位置 0 刚出发的时候），蜗蜗都会开心地看看自己距离下一棵植物还有多远，并记录下来。请你输出蜗蜗浇完所有植物最少走的总路程，和蜗蜗走的每一段路的长度，每一段路的长度指的是从目前的这棵植物（或者位置 0）到下一棵植物的路程。注意，因为蜗蜗一共要浇水 n 次，所以他会走 n 段路。

输入格式
第一行一个正整数 n。

第二行n个正整数 a1,a2,…,an ，表示 n 棵植物的位置。

输出格式
第一行， 表示蜗蜗浇完所有植物最少走的总路程。

接下来一行，为 n 个用空格隔开的整数，表示蜗蜗走的每一段路的长度。

样例输入
4
6 3 9 1
样例输出
9
1 2 3 3
样例解释
蜗蜗从位置 0 开始：

先走到位置 1，走的路程为 1； 然后走到位置 3，走的路程为 3−1=2； 然后走到位置 6，走的路程为 6−3=3； 最后走到位置 9，走的路程为 9−6=3。 最终蜗蜗走的总路程为 1+2+3+3=9。

数据范围
对于 100% 的数据，保证 1≤n≤104，1≤ai≤109 且 ai 互不相同。

Answer 1

该回答引用ChatGPT
C++ 的贪心算法实现，思路是将所有植物位置按照从小到大排序，然后从第二个位置开始，将当前位置减去前一个位置，求出每一段路的长度，并统计总路程。

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

using namespace std;

int main()
{
    int n;
    cin >> n;

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

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

    int total_distance = 0;
    vector<int> distances(n);
    distances[0] = a[0];
    for (int i = 1; i < n; ++i)
    {
        distances[i] = a[i] - a[i-1];
        total_distance += distances[i];
    }

    cout << total_distance << endl;

    for (int i = 0; i < n; ++i)
    {
        cout << distances[i] << " ";
    }

    return 0;
}