数组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; } 1234567891011121314151617181920212223242526272829303132333435363738 1234567891011121314151617181920212223242526272829303132333435363738