luogu-P1223 排队接水

GESP C++ 四级/五级练习题，贪心思想思想考点。题目难度⭐⭐★☆☆，适合五级入门和四级练习，洛谷难度等级普及-。

luogu-P1223 排队接水

题目要求

题目描述

有 $n$ 个人在一个水龙头前排队接水，假如每个人接水的时间为 $T_i$，请编程找出这 $n$ 个人排队的一种顺序，使得 $n$ 个人的平均等待时间最小。

一个人的等待时间不包括他的接水时间。

如果两个人接水的时间相同，编号更小的人应当排在前面。

输入格式

第一行为一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $T_i$ 表示第 $i$ 个人的接水时间 $T_i$。

输出格式

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

输入输出样例 #1

输入 #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

说明/提示

$1\le n \leq 1000$，$1\le t_i \leq 10^6$，不保证 $t_i$ 不重复。

题目分析

这是一道典型的贪心算法题目。

1. 问题分析

题目要求使 $n$ 个人的平均等待时间最小。因为 $n$ 是固定的，要使平均值最小，实际上就是要使总等待时间最小。

假设 $n$ 个人按某个顺序排队，接水时间分别为 $t_1, t_2, \dots, t_n$。

• 第 1 个人接水时，后面 $n-1$ 个人在等待，耗时 $t_1 \times (n-1)$。
• 第 2 个人接水时，后面 $n-2$ 个人在等待，耗时 $t_2 \times (n-2)$。
• …
• 第 $i$ 个人接水时，后面 $n-i$ 个人在等待，耗时 $t_i \times (n-i)$。

总等待时间 $S = \sum_{i=1}^{n} t_i \times (n-i)$。

2. 贪心策略

观察公式可以发现，越靠前的人，其接水时间 $t_i$ 被计算的次数越多（系数 $n-i$ 越大）。为了让总和 $S$ 最小，我们需要让耗时短的人排在前面，耗时长的人排在后面。即：按接水时间从小到大排序。

3. 细节处理

• 排序规则：题目要求“如果两个人接水的时间相同，编号更小的人应当排在前面”。因此在排序比较函数中，除了比较时间 time，还要处理 time 相等时比较 id 的情况。
• 数据范围：$n \le 1000, t_i \le 10^6$。总等待时间可能会达到 $1000 \times 1000 \times 10^6 / 2 \approx 5 \times 10^{11}$，超过了 int 的表示范围（约 $2 \times 10^9$），因此累加变量 sum 必须使用 long long 类型。
• 输出格式：平均等待时间需要保留两位小数，可以使用 printf("%.2f", ...) 或 fixed + setprecision(2)。

示例代码

#include <algorithm>
#include <iomanip>
#include <iostream>

typedef long long ll;
// 定义结构体Water，用于存储每个人的编号和接水时间
struct Water {
    int id;    // 人的编号
    int time;  // 接水所需时间
};

// 比较函数：按照接水时间从小到大排序
// 如果接水时间相同，则按照编号从小到大排序
bool cmp(Water a, Water b) {
    if (a.time == b.time) {
        return a.id < b.id;
    }
    return a.time < b.time;
}

struct Water t[1005];  // 数组大小大于1000，符合题目范围
int main() {
    int n;
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
        t[i].id = i;            // 记录初始编号
        std::cin >> t[i].time;  // 输入接水时间
    }
    // 贪心策略：接水时间越短的人排在越前面，能使后续所有人的等待时间总和最小
    std::sort(t + 1, t + n + 1, cmp);
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        std::cout << t[i].id << " ";
        // 计算总等待时间：
        // 第i个人接水时，排在他后面的 n-i 个人都在等待
        // 因此第i个人的时间贡献了 (n-i) 次等待
        sum += t[i].time * (n - i);
    }
    std::cout << "\n";
    // 输出平均等待时间，保留两位小数
    std::cout << std::setprecision(2) << std::fixed << (double)sum / n;
    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号