如何找到至少吃 P 个苹果所用的最短时间？请帮我优化这个问题的代码

Question

您好，请帮我解决这个问题。我还在下面附上了一个潜在的解决方案。我需要帮助来优化 java 中的代码。下面给出问题。

问题：

Varun's team participated in an eating competition at FoodContest in which they are asked to eat at least P apples. Varun's team consists of N members where a member i (1 <= i <= N ) takes Arr[i] minutes to eat a single apple. the task is to find the minimum time to eat at least P apples.

Note: A member can eat a apple any number of times.

例子

Sample Input:- n=4, p=10 , Arr[i] = {1 ,2 ,3 ,4}

Sample output: 6

Explanation:-

1st member will eat 6 apple , (ie, 1*6)

2nd member will eat 3 apple , (2*3)

3rd member will eat 2 apple , (3*2)

4th member will eat 1 apple , (4*1)

total = 12 ( total > p ) ie, team need atlest 6 min (minimum) to eat atleast 10 apples.

Sample Input:- n=7 ,p=7 , Arr[i] = { 1 ,1 ,1 ,1, 1, 1 ,1 }

Sample Output: 1

约束条件：-

1 <= N <= 10^5

1 <= Arr[i] <= 10

1 <= P <= 10^12

代码：（注意：我需要帮助来优化此代码并降低时间复杂度）

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


class Main {
    public static void main (String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");    
        String[] input = br.readLine().split(" "); 

        int n = Integer.parseInt(str[0]);  
        long p = Long.parseLong(str[1]);  
        long [] arr = new long [n];

        long max = 1000000000000L ;

        for(int i=0; i<n; i++) 
        {
            arr[i] = Long.parseLong(input[i]); 
        }
        
        
        for(long j=1;j<=max;j++){
            long sum=0;
            for(int i=0;i<n;i++){
                long rem=j/arr[i];
                sum=sum+rem;
                if(sum>=p){
                    System.out.println(j);
                    return;
                } 
            }  
        }

    }
}

Answer 1

说输入是 arr = {1, 2, 3, 4}, p = 60.

首先计算 least common denominator (LCD)，在本例中为12。

现在计算一下，在 12 分钟的时间内，每一分钟要吃多少个苹果：

Time	1	2	3	4	5	6	7	8	9	10	11	12
Member 1	1	2	3	4	5	6	7	8	9	10	11	12
Member 2	0	1	1	2	2	3	3	4	4	5	5	6
Member 3	0	0	1	1	1	2	2	2	3	3	3	4
Member 4	0	0	0	1	1	1	1	2	2	2	2	3
Total	1	3	5	8	9	12	13	16	18	20	21	25

用最后一行的值创建一个数组，即计算这个数组：

int[] total = { 0, 1, 3, 5, 8, 9, 12, 13, 16, 18, 20, 21, 25 };

您不需要存储每个成员的中间值。为清楚起见，它们仅显示在上面。

我们现在知道球队每 12 分钟吃 25 个苹果，所以总共吃 60 个苹果，我们至少需要 2 个完整回合。所以我们计算:

full rounds = p / 25 = 60 / 25 = 2
apples left = p % 25 = 60 % 25 = 10
time taken = 2 * 12 = 24 minutes
apples eaten = 2 * 25 = 50

现在对剩余苹果的计算数组进行二进制搜索，如果未找到完全匹配，则选择下一个更高的值。对于剩下的 10 个苹果，那就是 time = 6, total = 12.

这意味着我们还需要 6 分钟才能吃掉另外 12 个苹果，因此在 30 (24 + 6) 分钟内总共吃掉了 62 (50 + 12) 个苹果。

结果： 30 分钟。

现在祝你写这个算法的代码好运。

如何找到至少吃 P 个苹果所用的最短时间？请帮我优化这个问题的代码

How to find the minimum time taken to eat at least P apple ? Please Help me to optimize the code for this problem

java

binary-search

time-complexity

data-structures