MYF

UVa 10954 Add All

Posted on | In | | Visitors

题目链接

UVa 10954

方法：multiset erase单个位置的元素

题目分析

题目大意

给定n个数，每取两个数a、b，就要花费a+b元，然后把a、b两个数从这n个数中剔除，并且把a+b放入剩下的n-2个数中，形成n-1个数字。以此类推，问，把所有数都取完总个需要多少元。

解析

题目希望尽可能的贪心，把所有的数字都取出来，并且取的是最小的两个数字，所以第一反应是set，但是有重复数字怎么办？用multiset。但是multiset怎么erase呢？尝试了如果集合内容为{1,2,3,3,3,4}，erase(3)之后的结果是{1,2,4}，显然与我们想要的不符，所以新学了一招，erase单个元素的位置。具体方法如下。

1
2
3
4
multiset<int>st;	//我们定义的集合
multiset<int>::iterator it;	//定义迭代器
it=st.begin();	//找到想删除的元素的位置
st.erase(it);	//删之

掌握这个方法，这题就很好做了，取set的前两个数a、b，算出a+b，加到总cost里，然后再insert(a+b)，直至只有一个元素。

代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, n) for (int i = 1; i <= n; i++)
#define ForK(i, k, n) for (int i = k; i <= n; i++)
#define ForD(i, n) for (int i = n; i >= 0; i--)
#define Rep(i, n) for (int i = 0; i < n; i++)
#define RepD(i, n) for (int i = n; i >= 0; i--)
#define MemI(a) memset(a, 0, sizeof(a))
#define MemC(a) memset(a, '\0', sizeof(a))
#define vset(a,val) memset(a,val,sizeof(a))
#define pf          printf
#define sf(n)       scanf("%d", &n)
#define sff(a,b)    scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define PI acos(-1)
#define bug         pf("Hi----------\n")
#define eps 1e-8
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
using namespace std;
#define maxn 5005
int main(){
    int tmp,n,a,b,ans;
    while (sf(n),n) {
        ans=0;
        multiset<int>st;
        for (int i=0; i<n; i++) {
            sf(tmp);
            st.insert(tmp);
        }
        multiset<int>::iterator it;
        
        for (int i=0; i<n-1; i++) {
            it=st.begin();
            a=*it;
            st.erase(it);
            it=st.begin();
            b=*it;
            st.erase(it);
            st.insert(a+b);
            ans+=a+b;
        }
        cout<<ans<<endl;
    }
}