#C++2040——同学的等待

*******************************************************************************************************************

下课后第一件事情是干什么 ？当然是干饭啦 ！

不过干饭前我们先思考一个问题——怎样才能“光速”打饭 ？

场景引入：

假设你是打饭队伍里的任意一员（1~n）,对于你来说，是不是希望前面的同学打得越快越好，也就是等待时间越少越好。

那么要是每一个同学都能“得偿所愿”，是不是就能实现题目所说的最少等待时间呢。

但是偏偏就是有些慢吞吞的家伙排在你前面，这时候你又想，要是他们在我后面就好了。

哈哈，今天就浅浅施展一下魔法，满足你的两个愿望吧 ！（巴啦啦能量...）

有时候局部最优是能推出全局最优的，也就是贪心。

具体实现：

首先就把慢吞吞的家伙放到后面，也就是从小到大排序。

接着计算之后每一位同学的等待时间，累加即可。//特别的，第一位同学不需要等待时间，即temptime=0；

至于temptime的计算是一个前缀和的过程，这里迭代即可，不用记录每一位，如果用for循环回溯计算，则会超时。

样例解释如下：

注意事项:

等待时间（temptime）、等待总时间（totaltime）要开long long，数据量比较大。

参考代码:

#include <iostream>
#include <algorithm>
using namespace std;
int stutime[100005];
int main()
{
    long long n,totaltime=0,temptime=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>stutime[i];
    }
    sort(stutime,stutime+n,less<int>());//时间少的先打，后面少等 
    for(int i=1;i<n;i++)//第一个同学不用等待,即下标为0的同学
    {
        temptime+=stutime[i-1];//前缀和迭代
        totaltime+=temptime; //等待时间累加
    }
    cout<<totaltime;
    return 0;
 }