[210525]Greedy(大数の法則)

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n,m,k;
     n = sc.nextInt();
     m = sc.nextInt();
     k = sc.nextInt();

     int[] arr = new int[n];
     for(int i = 0; i<arr.length; i++){
       arr[i] = sc.nextInt();
     }

    Arrays.sort(arr);
    int first = arr[n-1];
    int sec   = arr[n-2];
    int cnt = 0;
    cnt = (m/(k+1));
    int sum = (first*k +  sec) * cnt + first*(m%(k+1));
/* 혹은 이 방법도 가능
    // 가장 큰 수가 더해지는 횟수 계산
    int cnt = (m / (k + 1)) * k;
    cnt += m % (k + 1);

    int result = 0;
    result += cnt * first; // 가장 큰 수 더하기
    result += (m - cnt) * second; // 두 번째로 큰 수 더하기
*/
    System.out.println(sum);    
  }
}

問題の説明
典型的な階調アルゴリズムの問題
入力値の最大数と2番目に大きい数を格納するだけでよい
ここではまず重複する数列を把握する
最大数と2番目の大数を加算する場合,特定の数列形式で一定の繰返し加算の特徴を持つ.
例えば、M=8、K=3(8回加算可能、3回連続加算可能)
繰り返し数列の長さはいくらですか?(int[]n={2,4,5,4,6}の場合)
6665/6665
正(K+1)は、上記の例では4である.
したがって,Mを(K+1)で割ったシェアは数列重複の回数となる.
ここでKを乗じると出現回数が最も多い
Mを考慮して(K+1)に分けない