最新要闻

广告

手机

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

英国房地产因利率上升陷入困境 房价正以2011年来最快速度下跌

 宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

宁夏评选出上半年10名“宁夏好人” 95后消防员因敬业奉献入选

家电

  1. 首页
  2. 移动通信
  3. 内容

P1223 排队接水

来源：博客园

题目描述

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

证明

如果要让所有人等待时间最短，那么就让打水速度快的人在前面

  • \(Part\) \(1\)

因为如果将等待时间较长的人往前排，他们就会占据水龙头的时间较长，后面的人等待的时间更长。


(资料图)

贪心算法的思路就是每次选择等待时间最短的人往前排。这样做的好处是，等待时间较短的人能够尽快接水，释放出水龙头，让后面的人能够更早开始接水，从而减少总体的平均等待时间。

在上面的代码中，我们使用了贪心策略，将等待时间从小到大进行排序，并按照这个顺序建立排队列。这样，等待时间较短的人会尽早进入队列，从而减少了总体的平均等待时间。

  • \(Part\) \(2\)

我们可以使用数学证明的方法来做这道题：

有 \(x\) 人，每个人打水时间为 \(x_{i}\) ，如果让打水速度快的人在前面,那么总时间为：

\[x_{1} (n-1) \times x_{2} (n-2) \cdots x_{i} (n-i)\]

如果要总时间最短，就让 \(x_{1} > x_{2} > x_{3} > \cdots > x_{n}\)

所以，要让平均排队时间最小，就要让打水快的人往前排

  • \(Part\) \(3\)

好的，让我们使用反证法来证明这个结论。

假设存在一种排队顺序，其中等待时间较长的人往前排，但是这种排队顺序的平均等待时间最小。

首先，我们先说明一个引理：

引理：在任何一个排队顺序中，如果我们交换了两个连续的人的位置，那么平均等待时间要么保持不变，要么减少。

证明：设原始排队顺序为 \(A, B, C, D, E, F\)，其中 \(A\) 的等待时间最长。交换 \(B\) 和 \(C\) 的位置，得到新的排队顺序为 \(A, C, B, D, E, F\)。我们假设交换位置后的新平均等待时间比原始平均等待时间更长。那么有：

\[\text{等待时间总和}(A) + \text{等待时间总和}(B,C) < \text{等待时间总和}(A, B, C)\]

但是，如果我们将 \(C\) 插入到 \(A\) 和 \(B\) 之间的位置，也就是得到新的排队顺序 \(A, C, B, D, E, F\)，根据平均等待时间的定义，我们可以得到：

\[\text{等待时间总和}(A, C) + \text{等待时间总和}(B) < \text{等待时间总和}(A, B, C)\]

与假设矛盾。所以，我们的假设是错误的，交换的位置并不会导致平均等待时间变长。

现在，我们使用反证法来证明假设的排队顺序不会使平均等待时间最小。

假设我们按照等待时间从小到大进行排序，依次为 \(A, B, C, D, E, F\)。其中，\(A\) 的等待时间最短，\(F\) 的等待时间最长，按照假设的排队顺序，我们将 \(A\) 放在了最后的位置。

现在，我们考虑将 \(A\) 移动到最前面的情况，即排队顺序为 \(A, B, C, D, E, F\)。

根据引理，我们知道这个新的排队顺序的平均等待时间要么保持不变，要么减少就平均等待时间而言，我们可以计算出初始排队顺序和新排队顺序的总等待时间，并比较两者的大小：

  • 初始排队顺序的总等待时间为 \(\text{等待时间}(A) + \text{等待时间}(B, C, D, E, F)\)
  • 新排队顺序的总等待时间为 \(\text{等待时间}(A, B, C, D, E, F)\)

如果新排队顺序的总等待时间小于初始排队顺序的总等待时间，则说明新排队顺序的平均等待时间也会更小。因此，假设的排队顺序不会平均等待时间最小。

根据反证法的原理，我们可以得出结论：要使平均排队时间最小，就要让打水快的人往前排。

算法原理

  • 贪心算法

为了找出平均等待时间最小的排队顺序，我们可以使用贪心算法。贪心算法的基本思想是在每一步选择局部最优解，最终得到全局最优解。

我们可以按照等待时间从小到大的顺序给人员进行排序。这样，等待时间最短的人员先接水，等待时间稍长一些的人员后接水。这样安排，可以使得整体的等待时间减少。

代码实现

#include#include#includeusing namespace std;#define N 1010int n,a[N]={0,},b[N];double t1,t2;int main(){  cin>>n;  for(int i=1;i<=n;i++)  {      cin>>a[i];      b[i]=a[i];  }   sort(a+1,a+n+1);  for(int i=1;i<=n;i++)  {      t1+=a[i-1];      t2+=t1;      for(int j=1;j<=n;j++)      {          if(a[i]==b[j])          {              cout<

tips

注意题目中的坑——两位小数

  • cout<(头文件#include);

  • printf("%.2f",a)（头文件就不说了）

关键词：