题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

JAVA 代码

/
* 最长字符串 s 的最短长度: 最下层叶节点到根节点的长度
/
//万能开头：
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[HTML_REMOVED]{
public long weight;
public int dep;
public Pair(long w , int d){
weight = w;
dep = d;
}

    @Override
    public int compareTo(Pair o) {
        if(weight != o.weight){
            if(weight < o.weight) return -1;
            return 1;
        }
        return dep - o.dep; //权重相同, 先选深度叶节点(最下层节点为叶节点)
    }
}
static Scanner sc = new Scanner(System.in);

public static void main(String []args){
    int n = sc.nextInt();
    int k = sc.nextInt();
    Queue<Pair> q = new PriorityQueue<Pair>();
    for(int i=0; i<n; i++ ){
        q.add(new Pair(sc.nextLong(),0));
    }
    while((n-1) % (k-1) != 0){
        q.add(new Pair(0l,0));
        n++;
    }
    long sum = 0;
    while(q.size() > 1){
        int min_dep = 0;
        long tmp = 0; 
        for(int i=0;i<k;i++){
            Pair p = q.poll();
            tmp += p.weight;
            min_dep = Math.max(p.dep, min_dep);
        }
        q.add(new Pair(tmp,min_dep + 1));
        sum+=tmp;
    }
    System.out.println(sum);
    System.out.println(q.peek().dep);
}

}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla