[プログラマー/CPP/JS]ベストコレクション

[程序]最适合的集合

1.質問

n個の自然数からなる繰り返し集合(複数の集合、都合のよい後に総称して「集合」と呼ぶ)では、以下の2つの条件を満たす集合を最適集合と呼ぶ.
各要素の和はSの数の集合である.
上記の条件を満たす各要素の積の最大の集合.
たとえば、2つの自然数の合計が9の4つのセットがあります.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
各要素の最大積{4,5}が最適な集合である.
セット内の要素の個数nとすべての要素の和sをパラメータとして指定した場合、最適なセットを返す解関数を完了します.

2.制限

最良のセットは、昇順に並べられた1次元配列(list,vector)を返します.
最適なセットが存在しない場合は、1次元配列(list,vector)に-1を入力して返します.
自然数の個数nは、1以上10000以下の自然数である.
すべての要素の合計は、1または10または1000000以下の自然数です.

3.解答

そのまま解けました.적절한 알고리즘이나 설명이 생각나지 않는다. 다 쓰고 보니 DP인 것 같기도..?

2つのアイデアで答えます.값들이 균등할 수록 곱의 최댓값이 커진다. 문제를 작게 쪼갤 수 있다.

一番いい集合が思いつかない場合.

nがsより大きい場合を除き、いずれも可能であるようであり、その場合のみ例外処理とする.

현재 가장 균등한 값 = s/n

s減算s/n、n減算1.
問題をs - s/nの和を持つn-1個数の最大積に変換する.

完了

この繰り返しn二.n2は2に等しく、2つに割って、そのまま並べることができます.

・n2であれば優先順位にn/2の値を挿入します.

nが偶数の場合はn/2を挿入します.

n奇数であれば挿入n/2+1더 해서 8이 되는 두 수 중 곱이 가장 큰 수는 (4, 4) 더 해서 9가 되는 두 수 중 곱이 가장 큰 수는 (4, 5)

終わってから並べ替えたいと思っていたのですが、並べずに通過するのを忘れてしまいました.

私が作成したアルゴリズムに従って均等に分配し、残りの分配は後にしなくてもよい.

4.最初のコードと異なる点

最初は鬼を利用して解決しようと思った.답이 안 나왔다.

初回合格、特に変化なし사실 난 천재가 아닐까?

5.コード

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, int s) {
    vector<int> answer;
    if(s < n) {
        answer.push_back(-1);
        return answer;
    }
    
    while(n > 2) {
        int result = s / n;
        answer.push_back(result);
        s -= result;
        n--;
    }
    answer.push_back(s/2);
    if(s%2==0){
        answer.push_back(s/2);
    }
    else{
        answer.push_back(s/2+1);
    }
    
    return answer;
}

6.コード（JS）

function solution(n, s) {
  const answer = [];
  while (n > 2) {
    const small = Math.floor(s / n);
    if (small === 0) return [-1];
    answer.push(small);
    s -= small;
    n -= 1;
  }
  answer.push(Math.floor(s / 2), Math.ceil(s / 2));

  return answer;
}

7.コード（失敗/JS）

function solution(n, s) {
  if (s < n) return [-1];
  
  const dfs = (len, target, res) => {
    if (len === 2) return [Math.floor(target / 2), Math.ceil(target / 2)];
    return [...res, Math.floor(target / len), ...dfs(len - 1, Math.ceil((target / len) * (len - 1)), res)];
  };

  return dfs(n, s, []);
}

top-downで簡潔なコードを書こうとしたが、効率の問題でパスできなかった.