【プログラミングコンテスト】AtCoder Beginner Contest 121③

花粉症の薬代のせいで3月は貧困生活中、ねむーです。

今回はAtCoder121(https://atcoder.jp/contests/abc121)にて開催されました、AtCoder Beginner Contest121の第3問「C - Energy Drink Collector」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

栄養ドリンクにレーティング上昇効果があると聞いた高橋くんは、 M 本の栄養ドリンクを買い集めることにしました。

栄養ドリンクが売られている店は N 軒あり、 i 軒目の店では 1 本 A i 円の栄養ドリンクを B i 本まで買うことができます。

最小で何円あれば M 本の栄養ドリンクを買い集めることができるでしょうか。

なお、与えられる入力では、十分なお金があれば M 本の栄養ドリンクを買い集められることが保証されます。

2.入力例

• 入力

1 100000
1000000000 100000

• 出力

100000000000000

3.初見の感想

• ソーティングしたいですが。金額と個数を別々の配列に保存するとメンドクサイです(金額と個数を紐づけたい)
• 今回はまとめるために構造体を使ってみます

4.コードの簡単な解説

• 入力を構造体にしてリストに入れます

struct Shop{
        public double price;
        public double num;
        public Shop(double price,double num)
        {
            this.price = price;
            this.num = num;
        }
    }
    static void Main(string[] args)
    {
        string[] temp = Console.ReadLine().Split(' ');
        double N = double.Parse(temp[0]);
        double M = double.Parse(temp[1]);

        var list = new List<Shop>();
        for (int i = 0; i < N; i++)
        {
            temp = Console.ReadLine().Split(' ');
            double price = double.Parse(temp[0]);
            double num = double.Parse(temp[1]);
            list.Add(new Shop(price, num));
        }

• 金額でソーティングします

        list.Sort((a, b) => a.price.CompareTo(b.price));

• 個数になるまで金額計算します

        double ans = 0;
        for(int i = 0; i < N; i++)
        {
            if (M >= list[i].num)
            {
                ans += list[i].price * list[i].num;
                M -= list[i].num;
            }
            else
            {
                ans += M * list[i].price;
                break;
            }
        }
        Console.WriteLine(ans);

6.全コード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct Shop{
        public double price;
        public double num;
        public Shop(double price,double num)
        {
            this.price = price;
            this.num = num;
        }
    }
    static void Main(string[] args)
    {
        string[] temp = Console.ReadLine().Split(' ');
        double N = double.Parse(temp[0]);
        double M = double.Parse(temp[1]);

        var list = new List<Shop>();
        for (int i = 0; i < N; i++)
        {
            temp = Console.ReadLine().Split(' ');
            double price = double.Parse(temp[0]);
            double num = double.Parse(temp[1]);
            list.Add(new Shop(price, num));
        }
        list.Sort((a, b) => a.price.CompareTo(b.price));
        double ans = 0;
        for(int i = 0; i < N; i++)
        {
            if (M >= list[i].num)
            {
                ans += list[i].price * list[i].num;
                M -= list[i].num;
            }
            else
            {
                ans += M * list[i].price;
                break;
            }
        }
        Console.WriteLine(ans);
    }

}

7.最後に

今回のABCはリアルタイム参加できなかったので残念(´・ω・｀)