有n位顾客同时等待一项服务，顾客i需要的服务时间为ti，设计贪心算法安排位顾客的服务次序，使得平均等待时间最小。请给出具体代码，并证明算法的正确性（平均等待时间=所有顾客等待时间之和/n）

这是一个典型的贪心算法问题，按照顾客需要服务的时间从小到大排序，并按顺序给顾客服务，可以得出平均等待时间最小。

具体代码如下：

def average_wait_time(n, t):
    # 按服务时间从小到大排序
    t = sorted(t)
    # 计算平均等待时间
    avg_wait_time = sum([(n - i) * t[i-1] for i in range(1, n+1)])
    return avg_wait_time / n

正确性证明：

设排序后的服务时间为t1,t2,...,tn，按照贪心策略依次服务，第i个顾客的等待时间为：

(ti+t1)+(ti+t2)+...+(ti+ti-1)

展开可得：

ti*i + (t1+t2+...+ti-1)

组合起来得到所有顾客的等待时间之和：

n*t1 + (n-1)*t2 + ... + t(n-1) + tn

因为平均等待时间等于所有顾客的等待时间之和除以n，所以我们的目标就是最小化上述等式。可以用数学归纳法证明，按照服务时间从小到大排序，并按顺序给顾客服务的贪心策略能够达到这一目标。

相关问题

最优服务次序问题。设有n个顾客同时等待一项服务，顾客i需要的服务时间为ti，应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。 给我该问题的算法思路描述，并用C/C++实现该算法。

该问题可以用贪心算法进行求解。具体思路是，将顾客按照所需要的服务时间从小到大排序，然后按照这个顺序进行服务。这样做的原因是，服务时间短的顾客可以快速得到服务，从而减少等待时间，而服务时间长的顾客可以在短时间内得到服务完成，也能减少等待时间。

以下是C++代码实现：

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int *t = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> t[i];
    }
    sort(t, t + n);  // 排序
    int sum = 0, ans = 0;
    for (int i = 0; i < n; i++) {
        sum += t[i];
        ans += sum;
    }
    cout << "最小平均等待时间为：" << ans / n << endl;
    delete[] t;
    return 0;
}

其中，输入n表示顾客数，接下来输入n个整数表示每个顾客需要的服务时间。我们首先将顾客按照服务时间从小到大排序，然后依次计算每个顾客的等待时间，并将等待时间累加起来。最后，将累加的等待时间除以n即可得到最小平均等待时间。

最优服务次序问题: 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1≤i≤n。共有s处可以提供此服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小平均等待时间是n个顾客等待服务时间的总和除以

n个顾客的个数，即：

$$\frac{\sum_{i=1}^{n}w_i}{n}$$

其中，$w_i$表示第$i$个顾客的等待时间。

这是一个经典的最优服务次序问题，可以使用贪心算法来解决。具体思路如下：

1. 将所有顾客按照需要的服务时间从小到大排序。

2. 对于每个顾客，将其分配到当前最短的服务时间的服务处，如果有多个服务处的服务时间相同，则选择编号最小的服务处。

3. 计算所有顾客的等待时间，并计算平均等待时间。

4. 如果还有未分配的顾客，回到第2步继续分配。

下面是该算法的Python实现：