51Nod 2133 排队接水

发表于 | 分类于 | 阅读次数: |
字数统计: 385 | 阅读时长 ≈ 1

排队接水

基准时间限制：1 秒 空间限制：131072 KB 分值: 5 难度：1级算法题 收藏 关注

描述

n个人一起排队接水，第i个人需要b[i]的时间来接水。
1 <= n <= 1000
0 <= b[i] <= 1000
同时只能有一个人接水，正在接水的人和没有接水的人都需要等待。
完成接水的人会立刻消失，不会继续等待。
你可以决定所有人接水的顺序，并希望最小化所有人等待时间的总和。

Input

第一行一个整数n
接下来n行，每行一个整数表示b[i]

Output

一行一个整数，表示所有人等待时间的总和的最小值

Input示例

3
1
2
3

Output示例

10

题解

贪心问题。要使所有人等待时间最小，则使接水时间最少的在最前面。每个人对所有人等待时间的贡献为这个人及在这个人之后的人的个数乘以这个人接水所需要的时间。由此可以得出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <utility>
#define ll long long

using namespace std ;

int main(){
    int n ;
    cin >> n ;
    vector<int> vec_ ;
    int tot = 0 ;
    for ( int i = 0 ; i < n ; i ++ ){
        int x ;
        cin >> x ;
        vec_.push_back(x) ;
    }
    sort(vec_.begin() , vec_.end()) ;
    for ( int i = 0 ; i < n ; i ++ ){
        tot += (n - i) * vec_[i] ;
    }
    cout << tot << endl ;
    return 0 ;
}