最も支払額が少なくなる際の購入代金のプログラム

実現したいこと

ここに実現したいことを箇条書きで書いてください。
n番目の商品を半額にすると最も金額が少なくなるプログラム

前提

listに入っている値を順番に半額にするアルゴリズムがわかりません。
現在入力するところまでのプログラムはできています。

（実現したいプログラム）
あなたはスーパーに買い物に来ています。
このスーパーでは現在半額セールが開催されており、購入した商品の中から一種類の商品を選び価格を半額にすることができます。
選んだ商品を複数個買っている場合は、その商品の複数個の合計金額が半額になります。
なお、半額にした際に小数点以下の金額が発生する場合、金額を切り上げします。

あなたは、 p1 円の商品を a1 個、 p2 円の商品を a2 個…と、全部で N 種類の商品を購入しようとしています。
半額セールを利用し、最も支払額が少なくなる際の購入代金を出力してください

入力される値

N
p_1 a_1
p_2 a_2
...
p_N a_N

制約

N,pi,ai：整数
1≤N≤10^4
1≤pi≤10^7
1≤ai≤10^7

サンプルケース1

[入力値]
4
80 7
500 1
20 10
30 17
[出力値]
1490

[説明]
半額にする商品をそれぞれ選ぶと、支払う金額は以下のようになります。
半額にする商品金額
1 : 1490
2 : 1520
3 : 1670
4 : 1515

1番目の商品を半額にすると最も金額が少なくなります。
よって、支払う金額の最小値は 1490 となります。

サンプルケース2

[入力値]
4
1000 5
1000 50
1000 567
1000 5432
[出力値]
3338000

サンプルケース3

[入力値]
3
11 3
15 7
299 1
[出力値]
288
[説明]
3 番目の商品を半額にすることで、支払う金額は最小となります。
299 の半額は 149.5 ですが、小数点以下の金額の場合切り上げ、 150 円とします。

該当のソースコード

java
1ソースコード
2public static void main(String[] args) {
3    Scanner scnn = new Scanner(System.in);
4    System.out.print("種類を入力してください：");
5    int N = scnn.nextInt();
6    int a, p;
7    List<Integer> list1 = new ArrayList<>();
8    List<Integer> list2 = new ArrayList<>();
9    for (int i = 0; i < N; i++) {
10        System.out.print("価格を入力してください：");
11        p = scnn.nextInt();
12        list1.add(i, p);
13
14        System.out.print("個数を入力してください：");
15        a = scnn.nextInt();
16        list2.add(i, a);
17    }
18    List<Integer> total = new ArrayList<>();
19    for (int i = 0; i < N; i++) {
20        total.add(list1.get(i)*list2.get(i));
21        System.out.println(list1.get(i) + " " + list2.get(i));
22    }
23}

1T2R3M4

2023/02/09 01:58

問題の出典はどこでしょうか。

fi4tb

2023/02/09 01:59

学校の課題です

episteme

2023/02/09 02:48

「total中の最大値」がわかれば、totalの総和 - total中の最大値/2 が求めるものではなくて?

行動規範の内容に同意します

回答1件

ベストアンサー

「i番目の商品を半額で買った場合の合計金額」は「すべての商品を定額で買った場合の合計金額」から「i番目の商品を半額することによって割り引かれる金額」を引くことにより求めることができます。これを利用してすべてのiについて、半額で買った場合の合計金額を計算し、その最小値を求めればよいです。

java
1Scanner scanner = new Scanner(System.in);
2
3// 入力を読み込む。
4int n = scanner.nextInt();
5long[] p = new long[n];
6long[] a = new long[n];
7for (int i = 0; i < n; i++) {
8    p[i] = scanner.nextLong();
9    a[i] = scanner.nextLong();
10}
11
12// すべての商品を定額で買った場合の金額を求める。
13long total = 0;
14for (int i = 0; i < n; i++) {
15    total += p[i] * a[i];
16}
17
18// i番目の商品を半額で買った場合の金額を計算し、その最小値を求める
19long min = Integer.MAX_VALUE;
20for (int i = 0; i < n; i++) {
21    // i番目の商品を半額で買った場合の合計金額
22    long price = total - (p[i]/2*a[i]);
23    min = Math.min(min, price);
24}
25
26System.out.println(min);