1 条题解

  • 0
    @ 2025-7-4 21:00:02

    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

    25年6月-华为实习(留学生)-2.最大营业额

    信息

    ID
    28
    时间
    1000ms
    内存
    256MiB
    难度
    3
    标签
    递交数
    3
    已通过
    1
    上传者