最短木板长度
真题目录: 点击去查看
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))
}
