求团队吃至少P个苹果的最短时间：Java代码优化求助

原代码存在的核心问题 #

• 时间复杂度严重超标：原代码采用逐一枚举时间从1到1e12的暴力思路，对每个时间点遍历所有团队成员计算可食用苹果总数，整体时间复杂度为O(T*N)，其中T最大可达1e12，N最大为1e5，总运算量超过1e17，完全无法在时间限制内完成运行。
• 边界设置存在漏洞：原代码将最大时间设为固定的1e12，当团队成员吃苹果速度普遍较慢时（如所有成员吃1个苹果需要10分钟，P为1e12），实际需要的时间会超过1e12，导致代码无法得到正确结果。

核心优化思路 #

• 利用问题单调性适配二分查找：如果时间为t时团队能吃掉至少P个苹果，那么所有大于t的时间下必然满足要求；反之如果t不满足要求，所有小于t的时间也必然不满足。基于该特征，无需逐一枚举时间，仅需在有效时间范围内二分查找满足条件的最小时间即可。
• 结合题目约束做校验优化：题目明确Arr[i]的取值范围为1到10，因此无需遍历所有N名成员计算总苹果数，只需统计每种吃苹果速度对应的人数，校验时仅需遍历1-10共10个速度值即可完成总苹果数计算，将单步校验的时间复杂度从O(N)压至常数级。
• 精准设置二分边界：找到团队中最快的成员（即吃单个苹果耗时最短的成员，对应速度值min_v），仅靠这名成员就能在min_v * P的时间内吃完P个苹果，因此将该值作为二分右边界，既保证覆盖所有可能的解，又避免无效的大范围查找。
• 累加过程提前剪枝：计算指定时间下的总苹果数时，一旦累计数量达到P，就停止后续计算，进一步减少运算量。

优化后代码实现 #

import java.io.*;
import java.util.*;

class Main {
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取输入的成员数n和目标苹果数p
        String[] str = br.readLine().split(" ");
        int n = Integer.parseInt(str[0]);
        long p = Long.parseLong(str[1]);
        String[] input = br.readLine().split(" ");
        
        // Arr[i]取值范围为1-10，用计数数组存储每个速度对应的成员数量
        long[] speedCount = new long[11]; // 下标1~10对应吃1个苹果的耗时
        for(int i=0; i<n; i++) {
            int speed = Integer.parseInt(input[i]);
            speedCount[speed]++;
        }
        
        // 找到最快成员的速度（即吃单个苹果耗时最短的数值）
        int minSpeed = 10;
        for(int v=1; v<=10; v++) {
            if(speedCount[v] > 0) {
                minSpeed = v;
                break;
            }
        }
        
        // 二分查找最小满足要求的时间
        long low = 1;
        // 右边界：最快成员单独吃完P个苹果所需的时间
        long high = (long) minSpeed * p;
        long ans = high;
        
        while(low <= high) {
            long mid = low + (high - low) / 2; // 避免整数溢出
            long totalApples = 0;
            // 计算mid时间内团队能吃的总苹果数
            for(int v=1; v<=10; v++) {
                if(speedCount[v] == 0) continue;
                totalApples += speedCount[v] * (mid / v);
                // 提前剪枝：已经达到目标苹果数就停止计算
                if(totalApples >= p) break;
            }
            if(totalApples >= p) {
                ans = mid;
                high = mid - 1; // 尝试寻找更小的可行时间
            } else {
                low = mid + 1; // 当前时间不足以完成目标，需要更长时间
            }
        }
        System.out.println(ans);
    }
}

优化效果对比 #

• 原代码时间复杂度：O(T*N)，T最大为1e12，N最大为1e5，运算量级别为1e17，完全无法通过时间限制。
• 优化后代码时间复杂度：O(N + logP * 10)，其中读入阶段遍历n个元素为O(N)，二分查找最多遍历log2(10*1e12)≈44次，每次校验仅需遍历1-10共10个速度值，整体运算量仅为十几万级别，完全适配题目给出的最大约束。

内容的提问来源于stack exchange，提问作者Ramoz