Расчет оптимального разделения для каждого элемента в массиве

Question

Предположим, что у меня есть массив положительных целых чисел, каждая из стоящих на длине стержня, например:

[26, 103, 59] 

Я хочу найти натуральное число размер, в котором я буду резать каждый из этих стержней. Я буду наказан за общее количество сокращений, которые я делаю, и на сумму остатков.

---

Пример

Например, если я вырезать стержни, длины которых, как указано выше, на куски длиной 6, я получите:

• стержня один (длина 26): 4 шт. + Остаток 2

• стержень два (длина 103): 17 штук + остаток 1

• стержень три (длина 59): 9 штук + остаточные 5

штрафы

• 4 + 17 + 9 = 30 порезы

• 2 + 1 + 5 = 8 остаток

---

Я хотел бы алгоритм взяв в качестве входов:

• массив длины стержня

• обрезанной штраф стоил

• остаток-штраф стоить

и выводит оптимальный размер разреза.

Answer 1

Это решение грубой силы, просто попробуйте.

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

public class Solution { 

    public static void main(String[] args) { 
     /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */ 
     Scanner s=new Scanner(System.in); 
     long c=s.nextLong(); 
     long pr=s.nextLong(); 
     long l=s.nextLong(); 
     long[] array=new long[(int)l]; 
     long max=0; 
     for(int x=0;x<l;x++){ 
      array[x]=s.nextLong(); 
      if(max<array[x]) 
        max=array[x]; 
     } 
     long ans=0; 
     for(int p=1;p<=max;p++){ 
      long sum=0; 
      long cut=0; 
      for(int q=0;q<l;q++){ 
       sum+=(array[q]/p); 
       if(array[q]%p==0){ 
       cut+=(array[q]/p)-1; 
       }else{ 
        cut+=(array[q]/p); 
       } 

      } 
      long cost=sum*p*pr-cut*c; 
      if(cost>ans) 
       ans=cost; 

     } 
     System.out.println(ans); 

    } 
}