最短木板长度

最短木板长度

真题目录: 点击去查看

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];// 将所有最短板补足到第二短板的长度，所需要总长度totalint 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 mathn, 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] = 1else: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]# 将所有最短板补足到第二短板的长度，所需要总长度totaltotal = 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 -= totalmin2[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];// 将所有最短板补足到第二短板的长度，所需要总长度totallet 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 mainimport ("fmt""sort"
)func getResult(m int, a []int) int {// 统计木板长度及其数量boardCount := make(map[int]int)for _, length := range a {boardCount[length]++}// 转换为切片，并按长度排序type board struct {length intcount  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.lengthtotalCost := diff * cur.countif totalCost > m {return cur.length + m/cur.count}m -= totalCostboards[i+1].count += cur.count}// 只剩下一种木板时，平分剩余 mreturn boards[len(boards)-1].length + m/boards[len(boards)-1].count
}func main() {var n, m intfmt.Scan(&n, &m)a := make([]int, n)for i := range a {fmt.Scan(&a[i])}fmt.Println(getResult(m, a))
}