春秋招笔试题总结
1.小红的花圃抬高方案
核心思路
对于给定的目标高度h，需要计算：
总土量 = sum(max(0, h - height[i]))
需要的车数 = ceil(总土量 / C)
总成本 = 总土量 * U + 车数 * F
判断成本是否 ≤ B
然后用二分查找找到最大可行高度。
代码实现
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 // 读取输入 long B = in.nextLong(); // 预算 long C = in.nextLong(); // 每车容量 long F = in.nextLong(); // 每车运输费 long U = in.nextLong(); // 单位填埋费 int n = in.nextInt(); // 花圃数 long[] heights = new long[n]; long minHeight = Long.MAX_VALUE; long maxHeight = Long.MIN_VALUE; for (int i = 0; i < n; i++) { heights[i] = in.nextLong(); minHeight = Math.min(minHeight, heights[i]); maxHeight = Math.max(maxHeight, heights[i]); } // 二分查找：下界是最低高度，上界可以设置得足够大 // 最坏情况：把最低的抬高到 maxHeight + B/U（但实际受预算限制） long left = minHeight; long right = maxHeight + 1000000000L; // 设置一个足够大的上界 long ans = minHeight; while (left <= right) { long mid = left + (right - left) / 2; if (check(mid, heights, B, C, F, U)) { ans = mid; left = mid + 1; // 尝试更高的高度 } else { right = mid - 1; // 降低高度 } } System.out.println(ans); } // 检查是否能将所有花圃抬高到目标高度 private static boolean check(long target, long[] heights, long B, long C, long F, long U) { long totalSoil = 0; // 计算需要的总土量 for (long h : heights) { if (h < target) { totalSoil += target - h; } } // 如果不需要土，成本为0 if (totalSoil == 0) { return true; } // 计算需要的车数：向上取整 long trucks = (totalSoil + C - 1) / C; // 计算总成本 long cost = totalSoil * U + trucks * F; return cost <= B; } }代码说明
输入读取：按照题目顺序读取 B, C, F, U, n 和 n 个高度
二分查找：
left设为最低高度（保证至少能达到当前最低高度）right设为一个足够大的值每次检查 mid 是否可行
检查函数 check：
计算所有花圃抬高到 target 所需的总土量
计算需要的车数（向上取整）
计算总成本并判断是否在预算内
输出答案：二分结束后输出最大的可行高度
注意事项
使用
long类型避免溢出（B 最大 10^11，计算过程中可能超过 int 范围）(totalSoil + C - 1) / C是整数向上取整的经典写法二分上界设置要足够大，考虑到最多可能抬高到初始最高高度 + 预算/单位填埋费