sicily 1016. 排队接水--课程作业

                                                                                1016. 排队接水

Time Limit: 1sec    Memory Limit:256MB

Description

有n个人在一个水龙头前排队接水，假如每个人接水的时间为t[i]，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
注意：若两个人的等待时间相同，则序号小的优先。

Input

第一行为n。
第二行共有n个整数,
分别表示第一个人到第n个人每人的接水时间t[1],t[2],t[3],t[4],……t[n]，每个数据之间有一个空格。

数据范围: 0<n<=1000, 0<t[i]<=1000

Output

共两行，第一行为n个数，以空格隔开，为一种排队顺序，即1到n的一种排列；

第二行为这种排列方案下的平均等待时间（保留到小数点后第二位）。

Sample Input

10

56 12 1 99 1000 234 33 55 99 812

Sample Output

3 2 7 8 1 4 9 6 10 5

291.90

首先要达到总体时间最小，我们只要看最后一个就可以知道，当最后一个人的等待时间最长时，总体等待时间会比最后一个人等待时间不是最长的短，因为前面的人的接水时间是要他后面的人一起等待的。所以我们只要给等待时间排个序就好了。
但是这里比较不好玩的就是，你还要记录它原来的顺序，那就是说，你在排序的时候还要同时交换它原来的顺序代号（可以理解为初始化是的数组的下标）。刚看到会觉得有点麻烦。
你应该还记得 map 吧，这题应该很快反应过来要用 map 的，因为它会自动根据 key 值来排序，省了你排序了。但是接水时间有重复，所以不能直接用 map，所以用 multimap。。。
下面是代码：

 #include <iostream>

 #include <stdio.h>

 #include <map>

 #include <utility>

 using namespace std;

 int main(int argc, char const *argv[])

 {

     int number, temp, i;

     multimap<int, int> waite;

     scanf("%d", &number);

     for(i = ; i <= number; i++) {//根据接水时间自动排序

         scanf("%d", &temp);

         waite.insert(make_pair(temp, i));

     }

     double sum = 0.0;

     multimap<int, int>::iterator iter = waite.begin();

     i = number - ;

     for (; iter != waite.end(); iter++) {

         //打印排队顺序

         if (i > )

             printf("%d ", iter->second);

         else

             printf("%d\n", iter->second);

         sum += (iter->first) * i;

         i--;

     }

     sum /= (double)number;

     printf("%.2lf\n", sum);

     return ;

 }

对于 i = number - 1;  而不是 i = numbe 个人觉得是接到水后等接满的过程中不算等。。。。