题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

O(MNlogN)

参考文献

yxc yyds !!!

JAVA 代码

/**
 * 暴力解法：
 *      每次合并两个序列, 时间复杂度为 O(n*n), 则需要合并m-1次, 那么则总的时间复杂度为 O(n*n*m) -> O(n*n*n)
 *      如何优化为 O(n*n)
 * 使用小顶堆
 *  分治法：
    每次合并两个序列, 两个序列n*n个数, 对这n*n个数进行分组;
    假设 第一个序列为 a[i], 第二个序列为b[i],对a序列进行排序
    分组如下：
    g[0] = b[0] + a[0] , ...... , b[0] + a[n]
                            |
                            |
                            ↓
    g[n] = b[n] + a[0] , ...... , b[n] + a[n]
    使用小根堆来存储每一组，更新每一个位置 
    n路归并之后，将结果存回到a序列中
 **/
//万能开头：
import java.util.Scanner;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.lang.Comparable;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.PriorityQueue;
import java.util.Queue;
class Main{
     static class Pair implements Comparable<Pair>{
        public Pair(int x, int y) {
            this.sum = x;
            this.pos = y;
        }
        public final int sum; 
        public final int pos;//当前在这个序列的下标

        @Override
        public int compareTo(Pair o) { //小根堆
            return sum - o.sum;
        }
    }
    static List<Integer> merge_n(List<Integer> list_a ,List<Integer> list_b){
        List<Integer>  res = new ArrayList<Integer>();
        Queue<Pair> q = new PriorityQueue<Pair>();
        //先取出每一组的第一个数
        for(int i=0;i<list_b.size();i++){
            q.add(new Pair(list_b.get(i) + list_a.get(0),0));
        }

        for(int i=0;i<list_a.size();i++){
            Pair p  = q.poll();
            res.add(p.sum);
            if(p.pos + 1 >= list_a.size())break;
            q.add(new Pair(p.sum - list_a.get(p.pos) + list_a.get(p.pos + 1),p.pos + 1));
        }
        return res;
    }

    static Scanner sc = new Scanner(System.in);
    public static void main(String []args){
        int T = sc.nextInt();
        while(T-- > 0 ){
            int m = sc.nextInt();
            int n = sc.nextInt();
            //先读入序列a
            List<Integer> list_a = new ArrayList<Integer>();
            for(int i=0;i<n;i++) list_a.add(sc.nextInt());
            Collections.sort(list_a);
            for(int i=1;i<m;i++){
                List<Integer>list_b = new ArrayList<Integer>();
                for(int j=0;j<n;j++) list_b.add(sc.nextInt());
                list_a = merge_n(list_a,list_b);
            }
            for(Integer ans: list_a){
                System.out.print(ans+" ");
            }
            System.out.println();
        }
    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla