124.作成できない金額

11466 ワード
アルゴリズム#アルゴリズム# テキストリンク
  • 董斌はN個の硬貨を持っている.この場合、N個のコインでプログラムを作成し、生成不可能な整数金額の最大値を求めてください.
    • 例えば、各硬貨がN = 5元であるとすると、
    作成できない整数金額のうち、最大値は8元です.

  • 入力条件

  • 第1行は、硬貨の個数を表す正の整数3, 2, 1, 1, 9を与える.(1 ≤ N ≤ 1,000)

  • 2行目には、1硬貨当たりの通貨単位を表すNの自然数が与えられ、各自然数はスペースで区切られている.
  • の場合、各通貨単位は1000000以下の自然数です.

  • しゅつりょくじょうけん
  • は、第1行目に与えられた硬貨から生成できない整数金額のうちの最大値を出力する.

    • 1.階調アルゴリズム

    

n = int(input())
data = list(map(int, input().split()))
data.sort()

target = 1
for i in data:
  #만들 수 없는 금액을 찾았을 때 반복 종료
  if target < i:
    break
  target += i

#만들 수 없는 금액 출력
print(target)
  • Nと仮定し、通貨単位はN = 4である.
    1)最初に,金額1が生成可能であることを確認するために1, 2, 3, 8に設定した.
    2)target = 1を満たしているか確認する.

  • 私たちはtarget = 1ドルのコインを持っています.このコインで1ドルを作ることができます.
  • 1
  • 1に更新
    • 3)target = 1 + 1 = 2を満たしているか確認する.

  • 私たちはtarget = 2ドルのコインを持っています.2.

  • 3まで作成できるすべての金額に等しい
    • 4)target = 2 + 2 = 4を満たしているか確認する.私たちは通貨単位target = 4の硬貨を持っています.3.
  • 6
    5)target = 4 + 3 = 7を満たしているか確認する.私たちは1枚の貨幣を持っていて、これよりもっと大きな弊害の単位はtarget = 7です.
    そのため、
  • の金額を作ることはできません.したがって、正解は8です.

    • 2.C++コード

    
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> arr;

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        arr.push_back(x);
    }

    sort(arr.begin(), arr.end());

    int target = 1;
    for (int i = 0; i < n; i++) {
        // 만들 수 없는 금액을 찾았을 때 반복 종료
        if (target < arr[i]) break;
        target += arr[i];
    }

    // 만들 수 없는 금액 출력
    cout << target << '\n';
}

    3.Javaコード

    
import java.util.*;

public class Main {

    public static int n;
    public static ArrayList<Integer> arrayList = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            arrayList.add(sc.nextInt());
        }

        Collections.sort(arrayList);

        int target = 1;
        for (int i = 0; i < n; i++) {
            // 만들 수 없는 금액을 찾았을 때 반복 종료
            if (target < arrayList.get(i)) break;
            target += arrayList.get(i);
        }

        System.out.println(target);
    }
}
    DRF-APIの実装を試みる
    ubuntuインストールboost 1.66.0