nthu 10925 - Advanced Heap Sort
http://140.114.86.238/problem/10925/ Description 有兩個序列S1和S2，各有N個元素。當我們在S1,S2各取一個數字時，總共會有NN這麼多可能的”和”(sum)。請找出這NN這麼多和裡最小的N個值，並將它們加總後輸出。
Input 只有一筆測資。
測試資料第一行為一個正整數N。
第二行有N個數字，以空白隔開，代表序列S1。
第二行有N個數字，以空白隔開，代表序列S2。
數字範圍：
0 < N < 10000
Output 輸出一行，N個最小的可能的和的加總。
Sample Input 5 1 3 5 7 9 2 4 6 8 10
EOF Sample Output 27 EOF
思路：贪心。先分别升序排列，枚举第一个数组，当枚举到第i个的时候，第二个数组的int(n*1.0/i+0.5)显然都没用。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年02月22日 星期一 16时26分18秒
4File Name :yzy.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E4+7;
34int n;
35int a[N];
36int b[N];
37int ans[N];
38multiset<int>se;
39multiset<int>::iterator it;
40int main()
41{// #ifndef ONLINE_JUDGE
42// freopen("code/in.txt","r",stdin);
43// #endif
44
45 scanf("%d",&n);
46 for ( int i = 1 ; i <= n ; i++)
47 {
48 scanf("%d",&a[i]);
49 }
50 for ( int i = 1 ; i <= n ; i++)
51 {
52 scanf("%d",&b[i]);
53 }
54 sort(a+1,a+n+1);
55 sort(b+1,b+n+1);
56
57// for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" "<<b[i]<<endl;
58
59 for ( int i = 1 ; i <= n ; i++)
60 {
61 for ( int j = 1 ; j <= ceil(n*1.0/i) ; j++)
62 se.insert(a[i]+b[j]);
63 }
64
65 LL sum = 0 ;
66 int cnt = 0 ;
67 for ( it = se.begin() ; it !=se.end() ;it++)
68 {
69 sum += *it;
70 // cout<<"*it:"<<*it<<endl;
71 cnt++;
72 if (cnt>=n) break;
73 }
74 cout<<sum<<endl;
75
76
77
78
79
80
81
82 return 0;
83}