最短木板长度

最短木板长度

真题目录: 点击去查看

E 卷 100分题型

题目描述

小明有 n 块木板，第 i ( 1 ≤ i ≤ n ) 块木板长度为 ai。
小明买了一块长度为 m 的木料，这块木料可以切割成任意块，拼接到已有的木板上，用来加长木板。
小明想让最短的模板尽量长。请问小明加长木板后，最短木板的长度可以为多少？

输入描述

输入的第一行包含两个正整数， n ( 1 ≤ n ≤ 10^3 ), m ( 1 ≤ m ≤ 10^6 )，n 表示木板数， m 表示木板长度。
输入的第二行包含 n 个正整数， a1, a2,…an ( 1 ≤ ai ≤ 10^6 )。

输出描述

输出的唯一一行包含一个正整数，表示加长木板后，最短木板的长度最大可以为多少？

用例1

输入

5 3
4 5 3 5 5

输出

5

说明

给第1块木板长度增加1，给第3块木板长度增加2后，这5块木板长度变为[5,5,5,5,5]，最短的木板的长度最大为5。

用例2

输入

5 2
4 5 3 5 5

输出

4

说明

给第3块木板长度增加1后，这5块木板长度变为[4,5,4,5,5]，剩余木料的长度为1。此时剩余木料无论给哪块木板加长，最短木料的长度都为4。

题解

要想让最短的木板尽可能长，那么我们就要不停地递进式补足最短板。

比如用例输入有5个板：4 5 3 5 5，可用材料m=3,最短的板长度是3，只有一个，那么我们就将他补足到4，此时消耗了一单位长度的材料，m=2,这样的话，只剩下两种长度的板4，5，且4长度有两个，5长度有三个，最短板是长度4.接下来我们应该尽量将最短板4长度的板补足到5长度，而刚好剩余材料m=2，可以将所有4长度的板补足到5长度，此时所有板都是5长度，且材料耗尽。

贪心算法

c++

#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<map>
#include<algorithm>
using namespace std;

int main() {
    int n,m;
    cin >> n >>m;
    vector<int> ans(n);
    for (int i = 0; i < n; i++) {
        cin >> ans[i];
    }
    
    sort(ans.begin(), ans.end());
    // 贪心算法
    while (m--) {
        int pos = 1;
        for (; pos < n; pos++) {
            if (ans[pos] > ans[pos-1]) {
                break;
            }
        }
        ans[pos-1]++;
    }

    cout << ans[0];
    return 0;
}

// 优化实现
#include<iostream>
#include<vector>
#include<string>
#include <utility> 
#include <sstream>
#include<map>
#include<algorithm>
#include<queue>
using namespace std;


struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.first > b.first; // first 值越大优先级越低
    }
};


int main() {
    int n,m;
    cin >> n >>m;
    vector<int> ans(n);
    map<int,int> mp;
    for (int i = 0; i < n; i++) {
        cin >> ans[i];
        mp[ans[i]]++;
    }
    
    // 小顶堆
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;
    for (auto p : mp) {
        pq.push({p.first, p.second});
    }
    while (m != 0) {
        pair<int,int> top = pq.top();
        // 都是同样长度，平均分
        if (pq.size() == 1) {
            int count = top.second;
            int num = top.first;
            // 会自定向下取整的
            int diff = m / count;
            pq.pop();
            pq.push({num+diff, count});
            break;
        } else {
            pq.pop();
            pair<int,int> se = pq.top();
            int diff = se.first - top.first;
            int count = top.second;
            
            if (diff * count <= m) {
                pq.pop();
                // 将值提升至se.fisrt消耗的长度
                pq.push({se.first, count + se.second});
                m -= diff * count;
            } else {
                // 这是数量写多少都不影响答案
                pq.push({top.first + (m / count), 1});
                break;
            }
        }
    }
    cout << pq.top().first;
}

JAVA

import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }

    System.out.println(getResult(m, a));
  }

  public static int getResult(int m, int[] a) {
    // 统计每种长度板的数量，记录到woods中，key是板长度，val是板数量
    HashMap<Integer, Integer> woods = new HashMap<>();
    for (Integer ai : a) {
      if (woods.containsKey(ai)) {
        Integer val = woods.get(ai);
        woods.put(ai, ++val);
      } else {
        woods.put(ai, 1);
      }
    }

    // 将统计到的板，按板长度排优先级，长度越短优先级越高，这里使用优先队列来实现优先级
    PriorityQueue<Integer[]> pq = new PriorityQueue<>((b, c) -> b[0] - c[0]);
    for (Integer wood : woods.keySet()) {
      pq.offer(new Integer[] {wood, woods.get(wood)});
    }

    // 只要还有剩余的m长度，就将他补到最短板上
    while (m > 0) {
      // 如果只有一种板长度，那么就尝试将m平均分配到各个板上
      if (pq.size() == 1) {
        Integer[] info = pq.poll();
        int len = info[0];
        int count = info[1];
        return len + m / count;
      }

      // 如果有多种板长度
      // min1是最短板
      Integer[] min1 = pq.poll();
      // min2是第二最短板
      Integer[] min2 = pq.peek();

      // diff是最短板和第二最短板的差距
      int diff = min2[0] - min1[0];
      // 将所有最短板补足到第二短板的长度，所需要总长度total
      int total = diff * min1[1];

      // 如果m的长度不够补足所有最短板，那么说明此时最短板的长度就是题解
      if (total > m) {
        return min1[0] + m / min1[1];
      }
      // 如果m的长度刚好可以补足所有最短板，那么说明最短板可以全部升级到第二短板，且刚好用完m，因此第二短板的长度就是题解
      else if (total == m) {
        return min2[0];
      }
      // 如果m的长度足够长，能补足所有最短板到第二短板，还能有剩余，则将最短的数量加到第二短板的数量上，继续下轮循环
      else {
        m -= total;
        min2[1] += min1[1];
      }
    }

    return pq.peek()[0];
  }
}

Python

# 输入获取
import math

n, m = map(int, input().split())
a = list(map(int, input().split()))


# 算法入口
def getResult(m, a):
    # 统计每种长度板的数量，记录到count中，属性是板长度，属性值是板数量
    count = {}
    for ai in a:
        if count.get(ai) is None:
            count[ai] = 1
        else:
            count[ai] += 1

    # 将统计到的板，按板长度升序
    arr = []
    for ai in count.keys():
        arr.append([int(ai), count[ai]])

    arr.sort(key=lambda x: x[0])

    # 只要还有剩余的m长度，就将他补到最短板上
    while m > 0:
        # 如果只有一种板长度，那么就尝试将m平均分配到各个板上
        if len(arr) == 1:
            lenV, count = arr[0]
            return lenV + math.floor(m / count)

        # 如果有多种板长度
        min1 = arr.pop(0) # min1是最短板
        min2 = arr[0] # min2是第二最短板

        # diff是最短板和第二最短板的差距
        diff = min2[0] - min1[0]

        # 将所有最短板补足到第二短板的长度，所需要总长度total
        total = diff * min1[1]

        # 如果m的长度不够补足所有最短板，那么说明此时最短板的长度就是题解
        if total > m:
            return min1[0] + math.floor(m / min1[1])
        # 如果m的长度刚好可以补足所有最短板，那么说明最短板可以全部升级到第二短板，且刚好用完m，因此第二短板的长度就是题解
        elif total == m:
            return min2[0]
        # 如果m的长度足够长，能补足所有最短板到第二短板，还能有剩余，则将最短的数量加到第二短板的数量上，继续下轮循环
        else:
            m -= total
            min2[1] += min1[1]

    return arr[0][0]


# 算法调用
print(getResult(m, a))

JavaScript

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 2) {
    const [n, m] = lines[0].split(" ").map(Number);
    const a = lines[1].split(" ").map(Number);
    console.log(getResult(m, a));

    lines.length = 0;
  }
});

function getResult(m, a) {
  // 统计每种长度板的数量，记录到count中，属性是板长度，属性值是板数量
  const count = {};
  for (let ai of a) {
    count[ai] ? count[ai]++ : (count[ai] = 1);
  }

  // 将统计到的板，按板长度升序
  const arr = [];
  for (let ai in count) {
    arr.push([ai - 0, count[ai]]);
  }
  arr.sort((a, b) => a[0] - b[0]);

  // 只要还有剩余的m长度，就将他补到最短板上
  while (m > 0) {
    // 如果只有一种板长度，那么就尝试将m平均分配到各个板上
    if (arr.length === 1) {
      const [len, count] = arr[0];
      return len + Math.floor(m / count);
    }

    // 如果有多种板长度
    // min1是最短板
    let min1 = arr.shift();
    // min2是第二最短板
    let min2 = arr[0];

    // diff是最短板和第二最短板的差距
    let diff = min2[0] - min1[0];

    // 将所有最短板补足到第二短板的长度，所需要总长度total
    let total = diff * min1[1];

    // 如果m的长度不够补足所有最短板，那么说明此时最短板的长度就是题解
    if (total > m) {
      return min1[0] + Math.floor(m / min1[1]);
    }
    // 如果m的长度刚好可以补足所有最短板，那么说明最短板可以全部升级到第二短板，且刚好用完m，因此第二短板的长度就是题解
    else if (total === m) {
      return min2[0];
    }
    // 如果m的长度足够长，能补足所有最短板到第二短板，还能有剩余，则将最短的数量加到第二短板的数量上，继续下轮循环
    else {
      m -= total;
      min2[1] += min1[1];
    }
  }

  return arr[0][0];
}

Go

package main

import (
	"fmt"
	"sort"
)

func getResult(m int, a []int) int {
	// 统计木板长度及其数量
	boardCount := make(map[int]int)
	for _, length := range a {
		boardCount[length]++
	}

	// 转换为切片，并按长度排序
	type board struct {
		length int
		count  int
	}

	boards := make([]board, 0, len(boardCount))
	for length, count := range boardCount {
		boards = append(boards, board{length, count})
	}
	sort.Slice(boards, func(i, j int) bool {
		return boards[i].length < boards[j].length
	})

	// 逐步填充最短板
	for i := 0; i < len(boards)-1; i++ {
		cur := boards[i]
		next := boards[i+1]

		// 计算当前木板与下一个木板的长度差距
		diff := next.length - cur.length
		totalCost := diff * cur.count

		if totalCost > m {
			return cur.length + m/cur.count
		}

		m -= totalCost
		boards[i+1].count += cur.count
	}

	// 只剩下一种木板时，平分剩余 m
	return boards[len(boards)-1].length + m/boards[len(boards)-1].count
}

func main() {
	var n, m int
	fmt.Scan(&n, &m)

	a := make([]int, n)
	for i := range a {
		fmt.Scan(&a[i])
	}

	fmt.Println(getResult(m, a))
}