HDU 6168 - Numbers 水题 2017 Multi-University Training Contest - Team 9

题目链接: HDU 6168 - Numbers

题目大意

数组a大小为n, 对于所有 i,j,1≤i<j≤n , 构成一个新数字a[i]+a[j], 放到b数组中 
最后将两个数组混在一起打乱, 给你打乱后的数, 求原来的a数组

思路

混合数组中最小两个数字一定是a中的数字, 因为没有比它们更小的数字来构成它们 
所以用一个multset存储所有数字, 这样每次取出来都是最小的数字并且方便删除 
先取出第一个数字, 放到数组a中, 并删除第一个数字 
然后从multset中一直取最小的数字(*S.begin()), 放到a数组中, 并从multset中删除它 
然后循环遍历a数组所有元素, 和刚取出来的那个数字相加, 得到的数字就是b数组中的一个数字, 从multset中erese掉(S.erase(S.lower_bound(ans[cnt-1]+ans[i])); 不能erase(ans[cnt-1]+ans[i]), 这样会把所有相同的值都删掉, 我们只需要删一个)

代码

858MS 7680K

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 125250 + 100;
int n, m, ans[maxn], cnt;int main()
{while(scanf("%d", &m) == 1){multiset<int> S;for(int i=0; i<m; ++i){int t;scanf("%d", &t);S.insert(t);}cnt = 0;ans[cnt++] = *S.begin();S.erase(S.begin());while(!S.empty()){ans[cnt++] = *S.begin();S.erase(S.begin());for(int i=0; i<cnt-1; ++i){S.erase(S.lower_bound(ans[cnt-1]+ans[i]));}}printf("%d\n", cnt);for(int i=0; i<cnt; ++i) printf("%d%c", ans[i], i==cnt-1 ? '\n' :' ');}return 0;
}
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
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