1 条题解
-
0
JAVA题解:
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] line = br.readLine().trim().split(" "); int n = Integer.parseInt(line[0]); // 小吃节持续天数 int K = Integer.parseInt(line[1]); // 总人力限制 int[] revenues = new int[n]; // 每天的营业额 int[] manpowers = new int[n]; // 每天的人力 for (int i = 0; i < n; i++) { line = br.readLine().trim().split(" "); revenues[i] = Integer.parseInt(line[0]); manpowers[i] = Integer.parseInt(line[1]); } System.out.println(maxRevenue(n, K, revenues, manpowers)); } /** * 计算在人力限制下的最大营业额 * * @param n 小吃节持续天数 * @param K 总人力限制 * @param revenues 每天的营业额 * @param manpowers 每天的人力 * @return 最大营业额 */ public static int maxRevenue(int n, int K, int[] revenues, int[] manpowers) { int maxRev = 0; // 最大营业额 int currentRev = 0; // 当前窗口的营业额 int currentMan = 0; // 当前窗口的人力 int left = 0; // 窗口左边界 // 滑动窗口 for (int right = 0; right < n; right++) { // 扩展窗口右边界 currentRev += revenues[right]; currentMan += manpowers[right]; // 当人力超过限制时,收缩窗口左边界 while (currentMan > K) { currentRev -= revenues[left]; currentMan -= manpowers[left]; left++; } // 更新最大营业额 maxRev = Math.max(maxRev, currentRev); } return maxRev; } /** * 另一种实现方式,使用双重循环直接枚举所有可能的连续天数 * 时间复杂度O(n^2),适用于小规模数据 */ public static int maxRevenueBruteForce(int n, int K, int[] revenues, int[] manpowers) { int maxRev = 0; // 枚举所有可能的起始日 for (int start = 0; start < n; start++) { int currentRev = 0; int currentMan = 0; // 枚举所有可能的结束日 for (int end = start; end < n; end++) { currentRev += revenues[end]; currentMan += manpowers[end]; // 如果人力不超过限制,则更新最大营业额 if (currentMan <= K) { maxRev = Math.max(maxRev, currentRev); } else { // 人力超过限制,无需继续扩展窗口 break; } } } return maxRev; } }
- 1
信息
- ID
- 28
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 3
- 标签
- 递交数
- 3
- 已通过
- 1
- 上传者