有n个人在一个水龙头前排队接水，假如每个人接水的时间为T 【i】 ，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。c++ 用例输入1：10 56 12 1 99 1000 234 33 55 99 812 用例输出1：3 2 7 8 1 4 9 6 10 5 291.90

<think>嗯，用户让我解决一个关于排队接水的问题，要求找出一种排队顺序，使得平均等待时间最小。需要我用C++来实现。首先，我得仔细理解问题。 题目是说，有n个人排队接水，每个人接水的时间是T[i]。要安排他们的顺序，让平均等待时间最小。平均等待时间应该是所有人的等待时间总和除以n，对吧？那怎么让这个总和最小呢？ 这时候，我应该想到，要让总等待时间最小，应该让接水时间短的人先接。因为后面的人等待的时间是前面所有人接水时间的总和。比如，如果有两个人，一个接1分钟，一个接2分钟。如果先接1分钟的，总等待时间是1（第一个人）+（1+2）（第二个人的等待时间）=4。如果反过来，总等待是2 + (2+1)=5。所以显然短的任务先处理更优。 那问题的解法应该是将接水时间从小到大排序，然后按照这个顺序处理。这样总等待时间就会最小。那平均等待时间自然也是最小的。 接下来需要考虑的是如何实现这个排序。因为题目中的输入是n个数，然后输出他们的排列顺序，比如用例输入1的输出是3 2 7...这些数字代表原数组中的位置。比如，第三个元素是1，所以排第一个。因此，我们需要记录每个时间对应的原始索引，然后在排序的时候按照时间升序排列，同时保留原始索引的信息。 那具体在C++中，如何处理呢？可以使用一个结构体或者pair来保存时间和对应的索引。例如，定义一个vector<pair<int, int>>，其中第一个元素是时间，第二个是原来的位置（注意，原题中的输入是按顺序给出的，所以索引应该是从1开始的）。然后对这个vector进行排序，按照时间的升序排列。如果时间相同的话，可能需要按照原来的顺序排，但题目用例中可能没有这种情况，但代码里应该处理这种情况，比如当时间相等时，按原位置升序排列。 排序之后，按顺序取出他们的原位置，就是所需的排列顺序。 然后计算总等待时间。比如，假设排序后的顺序是t1, t2, t3... tn，那么第一个人的等待时间是t1，第二个人的等待时间是t1 + t2，第三个的是t1 + t2 +t3，等等。总等待时间就是t1 + (t1 + t2) + (t1 +t2 +t3)+...+总和。这个总和可以简化为：t1*(n) + t2*(n-1) + ... + tn*1。因为第k个人的接水时间会被后面n -k个人等待。或者更直观地说，总等待时间等于每个时间乘以它后面的人数（包括自己？或者不包括？需要仔细算一下。） 例如，假设排序后的顺序是t1, t2, t3。总等待时间总和是 t1（第一个人的等待时间） + (t1 + t2)（第二个人的等待时间） + (t1 + t2 + t3)（第三个人的）。总和是3*t1 + 2*t2 +1*t3。所以，总等待时间等于每个时间乘以（n - i）的累加，其中i从0到n-1。或者说，第i个接水的人的时间会被后面n-i个人等待吗？或者，是前面的人已经接完了，后面的人的等待时间要加上前面的时间？ 可能更简单的方法是，总等待时间是各个人的等待时间的总和。每个人的等待时间等于他前面所有人接水时间的总和。例如，第一个人的等待时间是0，第二个人的等待时间是t1，第三个人的等待时间是t1 + t2，依此类推。或者题目中的等待时间是否包括自己的接水时间？比如，假设题目中的等待时间是指用户到达水龙头到开始接水的时间，或者是指从到达水龙头到接水结束的时间？ 这里可能需要明确问题中的“等待时间”的定义。比如，假设每个人一到水龙头就开始接水，那么第一个人的等待时间是0，第二个人必须等第一个人接完，所以等待时间是t1，第三个人等待t1 +t2，等等。这样总等待时间是0 + t1 + (t1 +t2) + ... + (t1+...+t_{n-1}) )。这样的话，总等待时间是t1*(n-1) + t2*(n-2) + ... + t_{n-1}*1。这个时候，总和等于sum_{i=1到n} t_i * (n -i)。或者，例如，对于第i个人（排序后的顺序），他的等待时间是前i-1个人的时间总和。总等待时间就是所有前i-1个人的总和之和。 举个例子，三个人的接水时间是t1, t2, t3，排序后的顺序是t1, t2, t3。那么总等待时间是0（第一个人） + t1（第二个人） + (t1 +t2)（第三个人）的总和。即总等待时间是 t1*2 + t2*1。所以总和等于t1*(3-1) + t2*(3-2) + t3*(3-3)。所以总等待时间是sum_{i=1到n} t_i*(n -i)。 所以，为了计算总等待时间，可以按照排序后的顺序，每个元素的t乘以（n - 当前的位置）的累加。比如，第一个元素的位置是0（索引），则乘以n-1-0？或者需要重新理清索引。或者，在循环时，对于第i个人（从0开始到n-1），他的接水时间t会贡献i次到后面的人的等待时间。比如，对于第0个人（第一个接水的），后面有n-1个人，他们的等待时间都包含t0。所以总贡献是 t0*(n-1 -0)。或者应该这样： 总等待时间等于，对于每个人i（在排序后的数组中），他的接水时间t_i会被后面所有的人（i+1到n-1）所等待。因此，总贡献是 t_i * (n - (i+1))。或者可能我之前举的例子中的总等待时间等于所有除了当前人的接水时间的总和？ 可能我之前的总和公式是正确的。例如，三个人的情况，总等待时间是 t1*2 + t2*1 + t3*0？显然不是，因为第三个人的等待时间是t1 + t2，所以总和应该是 t1 + (t1 + t2) = 2t1 + t2。所以总和等于 t1*(2) + t2*(1) + t3*0。这确实等于每个t_i乘以（n -i -1）的总和，其中i从0开始。例如，n=3，i=0时是t0*(3-0-1) = t0*2；i=1时是 t1*(3-1-1)=t1*1；i=2时是 t2*(3-2-1)=0。总和为2t0 + t1。所以这个总和等于总等待时间。因此，总等待时间的总和可以这样计算：排序后的数组中，每个元素t_i的贡献是 t_i * (n - i -1)，其中i从0到n-1。或者是不是？ 或者，可能更简单的方式是，总等待时间的总和等于每个接水顺序中的第k个元素（从1开始）的接水时间乘以（k-1）的总和？或者说，总等待时间的总和等于，除了最后一个接水的人之外，每个人的接水时间被后面的人等待的次数之和？ 比如，第一个人的接水时间被后面n-1个人等待，所以贡献是 t1*(n-1)。第二个人的被后面n-2个人，贡献t2*(n-2)。直到第n-1个人贡献t_{n-1}*0。最后一个不贡献。所以总和等于sum_{i=1到n} t_i*(n -i)。例如，当n=3时，总和是 t1*2 + t2*1 + t3*0。但这与前面例子中的总等待时间不符。前面的例子中总等待时间是 t1 + t1 + t2 = 2t1 + t2，这等于 t1*2 + t2*1 + t3*0。是的，所以总和等于sum t_i*(n-i)。那如果数组是按升序排列的话，这样的计算方式是正确的。所以正确的总等待时间总和的计算方式应该是，每个元素在排序后的数组中，乘以（该元素的位置之后的人数）的总和。或者更具体地说，在排序后的数组中的第i位（从1开始），该元素的接水时间会被后面n-i个人等待。例如，第一位的人会被后面的n-1个人等待，他们的等待时间都包括他的接水时间。所以总贡献是t_i * (n - i)。所以总和是所有元素的t乘以（n - i）的总和，其中i从1到n。或者，如果数组从0开始索引，那么是（n - i -1）吗？ 例如，排序后的数组是sorted，其中sorted[0]是第一个接水的人，sorted[1]是第二个，依此类推。总共有n个人。那么对于sorted[j]，他的接水时间会被后面n-j-1个人所等待。例如，j=0时，后面有n-1个人，所以贡献是 sorted[j].time * (n -1 -0) = sorted[j].time*(n-1)。而总等待时间总和就是每个sorted[j].time*(n-j-1)的总和？ 那假设数组是0-based的，那么总等待时间总和等于sum_{j=0到n-1} sorted[j].time * (n - j -1)。或者不是，比如之前的例子中，三个人的接水时间是t0, t1, t2。总等待时间总和是 t0*2 + t1*1 + t2*0。即j=0时，n-j-1=3-0-1=2，所以贡献是2*t0。j=1时，3-1-1=1，贡献t1*1。j=2时，3-2-1=0，贡献0。总和是2t0 +t1，这正好等于总等待时间。所以这个公式是对的。 所以，在代码中，首先需要将输入的数组按照升序排序，并记录原始的位置。然后计算总等待时间的总和，然后求平均值。 那么，在C++中如何实现？ 首先，读取输入。例如，用例输入1是10，然后是10个数字。所以先读n，然后读n个数字，存入数组。然后，将每个元素及其索引保存为一个pair的vector。例如，vector<pair<int, int>> vec，其中第一个元素是时间，第二个是原始位置（注意，题目中的输出是原始位置，所以索引应该从1开始）。 然后，对这个vector进行排序。排序的比较函数是，如果时间相同的话，按原始位置的升序排列。否则按时间的升序。比如，比较两个元素a和b，如果a.first < b.first，则排在前面。否则，如果相等的话，比较a.second < b.second。 这样，在排序之后，得到的就是按时间升序排列的顺序，时间相同的按原始位置升序。 接下来，计算总等待时间的总和。遍历排序后的数组，每个元素的time乘以（n - j -1）的总和，其中j是当前元素的索引（从0开始）。例如，总和初始化为0。循环j从0到n-1，sum += vec[j].first * (n - j -1)。总等待时间总和是这个sum。然后平均等待时间是sum / n，保留两位小数。 然后输出排序后的每个元素的原始位置，顺序是按排序后的顺序。例如，对于排序后的vec，依次输出vec[0].second, vec[1].second, ..., vec[n-1].second。用空格分隔。 现在，测试用例输入是： 输入1： 10 56 12 1 99 1000 234 33 55 99 812 这对应的原始位置是1到10。每个时间对应的原始位置如下： 索引（0-based） | 时间 | 原始位置 0 |56 → 1 1 |12 →2 2 |1 →3 3 |99 →4 4 |1000 →5 5 |234 →6 6 |33 →7 7 |55 →8 8 |99 →9 9 |812 →10 排序后的顺序是按时间升序，时间相同的按原始位置升序。时间依次是： 时间1（原位置3），时间12（原2），时间33（原7），时间55（原8），时间56（原1），时间99有两个，原位置4和9，所以按原位置排序，4在前。然后是234（原6），812（原10），99（原9？或者原位置是9的时间是99，原4的时间是99？原输入中的第4个元素是99？原输入中的索引3是99，原位置是4吗？原输入的数组是输入的十个数，索引从0到9，对应的原位置是1到10吗？ 是的。比如，输入的十个数，索引0对应原位置1，索引1对应原位置2，以此类推。所以，原输入中的第三个元素（索引2）是1，原位置是3。是的。 所以，排序后的时间顺序应该是： 1（原3），12（原2），33（原7），55（原8），56（原1），99（原4），99（原9），234（原6），812（原10），1000（原5）。对吗？ 比如，两个99的时间，原位置是4和9。在排序时，时间相同的情况下，按原位置升序，所以原4（时间99）排在原9之前。所以，排序后的顺序是： 时间：1 →12 →33 →55 →56 →99 →99 →234 →812 →1000 对应的原位置：3，2，7，8，1，4，9，6，10，5。 那用例输出1的顺序是3 2 7 8 1 4 9 6 10 5，这与这个排序后的顺序一致。那么总等待时间的总和是： 每个时间乘以（n -j -1），其中j从0到9，n=10。所以： j=0，时间1 →贡献1*(10-0-1)=9 →1*9=9 j=1，时间12 →12*(10-1-1)=12*8=96 →总和9+96=105 j=2，时间33 →33*(10-2-1)=33*7=231 →总和105+231=336 j=3，时间55 →55*6=330 →总和336+330=666 j=4，时间56 →56*5=280 →666+280=946 j=5，时间99 →99*4=396 →946+396=1342 j=6，时间99 →99*3=297 →1342+297=1639 j=7，时间234 →234*2=468 →1639+468=2107 j=8，时间812 →812*1=812 →2107+812=2919 j=9，时间1000 →1000*0=0 →总和2919. 总等待时间是2919。平均等待时间是2919 /10 =291.9，即输出291.90，符合用例的输出。 所以，这样的计算是正确的。 现在，如何将这些步骤转化为C++代码？ 步骤： 1. 读取n，然后读取n个数存入数组。 2. 创建一个vector的pair，保存时间和原位置。注意原位置是i+1，因为输入是按1开始的顺序。 3. 对vector进行排序：首先按时间升序，如果时间相同，按原位置升序。 4. 输出排序后的原位置顺序，用空格分隔。 5. 计算总等待时间总和，然后输出平均值，保留两位小数。 代码实现： 首先，输入处理： #include <iostream> #include <vector> #include <algorithm> #include <iomanip> // 用于输出保留两位小数 using namespace std; int main() { int n; cin >> n; vector<pair<int, int>> times; // 存储时间和原位置 for (int i = 0; i < n; ++i) { int t; cin >> t; times.emplace_back(t, i + 1); // 原位置是i+1 } // 排序：时间升序，时间相同则原位置升序 sort(times.begin(), times.end(), [](const pair<int, int>& a, const pair<int, int>& b) { if (a.first == b.first) { return a.second < b.second; } return a.first < b.first; }); // 输出排序后的原位置 for (int i = 0; i < n; ++i) { if (i > 0) cout << " "; cout << times[i].second; } cout << endl; // 计算总等待时间总和 long long total_wait = 0; for (int j = 0; j < n; ++j) { total_wait += times[j].first * (n - j - 1); } // 计算平均值，保留两位小数 double average = static_cast<double>(total_wait) / n; cout << fixed << setprecision(2) << average << endl; return 0; } 这样应该就能得到正确的结果了。 测试用例输入1的输出是3 2 7 8 1 4 9 6 10 5，总等待时间2919，平均291.90，所以代码是正确的。 需要注意的是，总等待时间的变量类型应该足够大，因为当n很大且每个时间很大时，可能会溢出。所以用long long比较安全。 另外，排序时的比较函数是否正确处理了时间相等的情况。例如，当两个时间相等时，按原位置升序排列。这在代码中已经处理了。 综上，这样的代码应该能正确解决问题。</think>要解决这个问题，我们需要找到一种排队顺序，使得平均等待时间最小。核心思路是将接水时间较短的人排在前面，从而减少后续所有人的等待时间总和。 ### 方法思路 1. **贪心策略**：将接水时间按升序排列。短任务优先处理，可减少后续任务的累积等待时间。 2. **索引处理**：排序时需保留原始索引，以便输出正确的顺序。 3. **等待时间计算**：总等待时间是每个人接水时间乘以其后的人数之和。例如，第一个人接水时间为$t_1$，后面有$n-1$人需等待$t_1$，总贡献为$t_1 \times (n-1)$。 ### 解决代码 ```cpp #include <iostream> #include <vector> #include <algorithm> #include <iomanip> using namespace std; int main() { int n; cin >> n; vector<pair<int, int>> times; // 存储时间和原始位置 for (int i = 0; i < n; ++i) { int t; cin >> t; times.emplace_back(t, i + 1); // 原始位置从1开始 } // 排序规则：时间短的优先，时间相同则原始位置靠前的优先 sort(times.begin(), times.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return (a.first == b.first) ? (a.second < b.second) : (a.first < b.first); }); // 输出排序后的原始位置 for (int i = 0; i < n; ++i) { if (i > 0) cout << " "; cout << times[i].second; } cout << endl; // 计算总等待时间 long long total_wait = 0; for (int j = 0; j < n; ++j) { total_wait += times[j].first * (n - j - 1); } // 计算并输出平均等待时间，保留两位小数 double average = static_cast<double>(total_wait) / n; cout << fixed << setprecision(2) << average << endl; return 0; } ``` ### 代码解释 1. **输入处理**：读取接水人数和每个人的时间，保存时间和原始位置。 2. **排序**：按时间升序排列，时间相同则按原始位置升序。 3. **输出顺序**：按排序后的顺序输出原始位置。 4. **计算等待时间**：遍历排序后的数组，累加每个人时间乘以其后的人数，得到总等待时间。 5. **平均值计算**：总等待时间除以人数，保留两位小数输出。 该方法通过贪心策略确保了总等待时间最小，时间复杂度为$O(n \log n)$，主要由排序操作决定。