Problem Description
The procedure Merge(L1,L2:in List_type;L:out List_type) that we have in mind for sorting two lists is described as follows. Initialize pointers to the first item in each list L1,L2, and then
repeat
compare the two items pointed at;
move the smaller into L;
move the pointer which originally points at the smaller one to the next number;
until one of L1,L2 exhausts;
drain the remainder of the unexhausted list into L;
Now let us come to the situation when there are k pointers, here k≥2. Let L be a list of n elements. Divide L into k disjoint contiguous sublists L1,L2,…,Lk of nearly equal length. Some Li’s (namely, n reminder k of them, so possibly none) will have length , let these have the low indices: L1,L2,…,Ln%k Other Li’s will have length
, and high indices are assigned: Ln%k+1,…,Lk-1,Lk. We intend to recursively sort the Li’s and merge the k results into an answer list.
We use Linear-Search-Merge here to merge k sorted lists. We find the smallest of k items (one from each of the k sorted source lists), at a cost of k-1 comparisons. Move the smallest into the answer list and advances its corresponding pointer (the next smallest element) in the source list from which it came. Again there are k items, from among which the smallest is to be selected. (When i (1 ≤ i < k) lists are empty, k-way merging sort becomes to (k-i)-way merging sort, and the draining process will start when the total order of all the elements have been found)
Given a list containing n elements, your task is to find out the maximum number of comparisons in k-way merging sort.
Input
Output
Sample Input
Sample Output
import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner; public class Main{
static Map<BigInteger,BigInteger>dp = new HashMap<BigInteger,BigInteger>();
static BigInteger n, ans;
static int k;
static BigInteger dfs(BigInteger len, BigInteger x){
if(dp.containsKey(len)) return x.multiply(dp.get(len));
if(len.compareTo(BigInteger.valueOf(k))<=0){
return x.multiply(len.subtract(BigInteger.ONE)).multiply(len).divide(BigInteger.valueOf(2));
}
BigInteger tmp = (BigInteger.valueOf(k).subtract(BigInteger.ONE)).multiply((len.subtract(BigInteger.valueOf(k))));
tmp = tmp.add(BigInteger.valueOf(k).multiply(BigInteger.valueOf(k).subtract(BigInteger.ONE)).divide(BigInteger.valueOf(2)));
BigInteger kk = len.mod(BigInteger.valueOf(k));
if(kk!=BigInteger.ZERO){
tmp=tmp.add(dfs(len.divide(BigInteger.valueOf(k)).add(BigInteger.ONE),kk));
}
tmp = tmp.add(dfs(len.divide(BigInteger.valueOf(k)),BigInteger.valueOf(k).subtract(kk)));
dp.put(len, tmp);
return tmp.multiply(x);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for(int cas=1; cas<=T; cas++){
dp.clear();
n = in.nextBigInteger();
k = in.nextInt();
ans=dfs(n, BigInteger.ONE);
System.out.println("Case "+cas+": "+ans);
}
}
}
下面这个是我先用c++写的版本，用来验证算法，上面的java是用这c++代码改写的（其实一样）。
#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <map>
using namespace std;
typedef long long LL;
LL n,k;
map<LL,LL>mp; LL dfs(LL len,LL x)
{
if(mp.count(len)) return x*mp[len];
if(len<=k) return x*(len-)*len/;
LL tmp=(k-)*(len-k);
tmp+=k*(k-)/;
tmp+=dfs(len/k+(len%k!=),(len%k));
tmp+=dfs(len/k,(k-len%k));
mp[len]=tmp;
return tmp*x;
} int main()
{
while(scanf("%lld%lld",&n,&k)!=EOF)
{
mp.clear();
LL ans=dfs(n,);
cout<<"final ans = "<<ans<<endl;
}
return ;
}