IMGP7062 / 丹波写眞 Tamba photo
ギフトがどうとか、予算がどうとか、寄付金の最大金額が小さくなるようにとか。
それって簡単に言えば年貢でしょ?
www.codingame.com
年貢を徴収するぞ!
説明を読んでもいまいち要領を得ないので*1、
「年貢の話かな?」と頭の中で置き換えたらできた。
要は全村に均等に負担させつつ徴収目標を達成する、ってことですよね。
Source code
using System; using System.Linq; using System.IO; using System.Text; using System.Collections; using System.Collections.Generic; /** * Auto-generated code below aims at helping you parse * the standard input according to the problem statement. **/ class Solution { static void Main(string[] args) { //村の数 int N = int.Parse(Console.ReadLine()); //徴収する年貢の総量 int C = int.Parse(Console.ReadLine()); //村の収穫量リスト作成 int[] v = new int[N]; for (int i = 0; i < N; i++) { v[i] = int.Parse(Console.ReadLine()); } //収穫量の昇順ソート Array.Sort(v); //年貢の平均負担量 int Ave = C / N; //余り int q = C % Ave; //村々をまわる for (int i = 0; i < N - 1; i++) { //収穫分から年貢を徴収する int remain = v[i] - Ave; if (remain >= 0) //年貢を払えるなら { //総徴収量から負担分を引いて更新する C -= Ave; //Output用に書き換える v[i] = Ave; } else { //払えないのなら //あるだけ根こそぎ奪う C -= v[i]; } //再び残りから平均負担量と余りを求める(足りない分は別から村から取る) Ave = C / (N - (i + 1)); if (Ave > 0) { q = C % Ave; } else { q = 0; } } if (Ave + q > v[v.Length - 1]) //最後の村の年貢が足りなければ { Console.WriteLine("IMPOSSIBLE"); } else { //年貢が足りるなら v[v.Length - 1] = Ave + q; foreach (int n in v) { Console.WriteLine(n); } } } }
- 作者: 渡辺尚志
- 出版社/メーカー: KADOKAWA / 角川学芸出版
- 発売日: 2015/12/25
- メディア: Kindle版
- この商品を含むブログを見る
*1:英語だから