打水问题,大家进来看看~
http://acm.jlu.edu.cn/joj/showproblem.php?pid=2657

一口古井边有n个人在排队打水。由于办事效率不同，他们每个人打水的时间有长有短，分别是t1，t2，t3……tn。一个人打水 的等待时间是指他排在队伍里空等的时间（打水时间不算）。现在要你将这n个人重新排个队打水，使得所有人的等待时间总和 最少，求出那个最少的等待时间总和。

Input
输入包含多个case, 每个case包含两行，第一行包含一个整数n，不超过500。第二行包含n个整数，即每个人的打水时间t[i] ( 0<=t[i]<=60 )。以 EOF 结束

Output
每行输出一个整数，即最少等待时间总和。

Input
3
2 3 1
Output
4


JOJ上的一道题,
我的想法是贪心,把打水时间放在最前面,即从小到大排序,不知道这么想有没有错?各位验证下~
排序完毕后,
时间总和=t[0]+(t[0]+t[1])+(t[0]+t[1]+t[2])+...
即=第1个人的等待时间+第2个人的等待时间+第3个人的等待时间+...
我WA的代码:

C/C++ code

#include <stdio.h>#include <stdlib.h>int cmp(const void *a,const void *b){    return *(int *)a-*(int *)b;}int main(){    int time[500];    int n,i;    long long sum;    while(scanf("%d",&n)!=EOF)    {        for(i=0;i<n;i++)            scanf("%d",&time[i]);        qsort(time,n,sizeof(int),cmp);        for(i=0,sum=0;i<n-1;i++)            sum+=(sum+time[i]);        printf("%lld\n",sum);    }    return 0;}

[解决办法]
想法一样，应该就是这样
[解决办法]

探讨

哈哈 很不错哦

[解决办法]
sum+=(sum+time[i]);
楼主这里是错的，其他没什么.

C/C++ code

#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){    int n,t;    vector<int> time;    while(cin>>n)    {        for(int cnt=1;cnt<=n;++cnt)        {            cin>>t;            time.push_back(t);        }        sort(time.begin(),time.end());        int sum=0,total=0;        for(int cnt=1;cnt<n;++cnt)        {            sum=sum+time[cnt-1];            total+=sum;        }        cout<<total<<endl;        time.clear();    }}