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)显然都没用。
/* ***********************************************
Author :111qqz
Created Time :2016年02月22日 星期一 16时26分18秒
File Name :yzy.cpp
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E4+7;
7int n;
8int a[N];
9int b[N];
10int ans[N];
11multiset<int>se;
12multiset<int>::iterator it;
13int main()
14{// #ifndef ONLINE_JUDGE
15// freopen("code/in.txt","r",stdin);
16// #endif
1 scanf("%d",&n);
2 for ( int i = 1 ; i <= n ; i++)
3 {
4 scanf("%d",&a[i]);
5 }
6 for ( int i = 1 ; i <= n ; i++)
7 {
8 scanf("%d",&b[i]);
9 }
10 sort(a+1,a+n+1);
11 sort(b+1,b+n+1);
// for ( int i = 1 ; i <= n ; i++) cout<<a[i]<<" "<<b[i]<<endl;
1 for ( int i = 1 ; i <= n ; i++)
2 {
3 for ( int j = 1 ; j <= ceil(n*1.0/i) ; j++)
4 se.insert(a[i]+b[j]);
5 }
1 LL sum = 0 ;
2 int cnt = 0 ;
3 for ( it = se.begin() ; it !=se.end() ;it++)
4 {
5 sum += *it;
6 // cout<<"*it:"<<*it<<endl;
7 cnt++;
8 if (cnt>=n) break;
9 }
10 cout<<sum<<endl;
return 0;
}