プログラマ-最適な集合
7148 ワード
問題の説明
n個の自然数からなる繰返し集合のうち、以下の2つの条件を満たす集合を最適集合と呼ぶ.
各要素の和はSの数の集合である.
上記の条件を満たす各要素の積の最大の集合.
たとえば、2つの自然数の合計が9の4つのセットがあります.
{ 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 }
各要素の最大積{4,5}が最適な集合である.
セット内の要素の個数nとすべての要素の和sをパラメータとして指定した場合、最適なセットを返す解関数を完了します.
せいげんじょうけん
∙最良の集合は、昇順に並べられた1次元配列(list,vector)を返してください.
∙最適なコレクションが存在しない場合は、1次元配列(list,vector)に-1を入力して返します.
∙自然数の個数nは、1以上10000以下の自然数である.
∙すべての要素の合計は1以上、10000000以下の自然数です.
I/O例説明
I/O例#1
問題の例.
I/O例#2
2つの自然数は1つと1つの集合を構成することはできない.したがって、-1を含む配列が返されます.
I/O例#3
2つの自然数の集合のうち、要素の和が8の集合は以下の通りである.
{ 1, 7 }, { 2, 6 }, { 3, 5 }, { 4, 4 }
各要素の最大積{4,4}は最適な集合である.
function solution(n, s) {
let answer = [];
let i = 0;
let average = Math.floor(s / n);
let extra = s % n;
if( average === 0) return [-1];
while( i < n){
answer.push(average);
i++;
}
if(extra){
for( let j = 0; j < extra; j++){
answer[j] += 1;
}
}
answer.sort( (a, b) => a - b);
return answer;
}
任意の配列の自然数のすべての要素に最大値を乗算し、偏差をできるだけ小さくする必要があります.したがって,平均n個の要素に割り当てられ,残りの演算子の残り値を1で割って配列の前から加算する.最後に昇順で終わる変数宣言は、割当てが完了した後、averageが0の場合、n個の自然数として表されるため、直ちに[1]を返す.
前回一番お尻の問題を間違えたので簡単に解決できました
+) python version
import math
def solution(n, s):
answer = []
i = 0
average = math.floor(s / n)
extra = s % n
if average == 0: return [-1]
while i < n:
answer.append(average)
i += 1
if extra:
for j in range(0, extra):
answer[j] += 1
answer.sort()
return answer
Reference
この問題について(プログラマ-最適な集合), 我々は、より多くの情報をここで見つけました https://velog.io/@skkfea07/programmers-최고의-집합テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol