FZU 1919 -- K-way Merging sort(记忆化搜索)
2018-06-17 21:49:45来源:未知 阅读 ()
题目链接
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-1)*len/2; LL tmp=(k-1)*(len-k); tmp+=k*(k-1)/2; tmp+=dfs(len/k+(len%k!=0),(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,1); cout<<"final ans = "<<ans<<endl; } return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- FZU - 2295 Human life (最大权闭合子图) 2019-08-16
- kuangbin专题 专题一 简单搜索 Fire Game FZU - 2150 2019-08-16
- 洛谷P1919 【模板】A*B Problem升级版(FFT快速傅里叶) 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash