結果
問題 | No.198 キャンディー・ボックス2 |
ユーザー |
![]() |
提出日時 | 2016-07-21 03:26:33 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 27 ms / 1,000 ms |
コード長 | 2,625 bytes |
コンパイル時間 | 5,862 ms |
コンパイル使用メモリ | 114,492 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-11-16 10:03:56 |
合計ジャッジ時間 | 4,186 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections.Generic; using System.Text; using System.Linq; class Program { public void Proc() { Reader.IsDebug = false; Temoti = long.Parse(Reader.ReadLine()); int boxCount = int.Parse(Reader.ReadLine()); this.BoxList = new long[boxCount]; Total = 0; for(int i=0; i<boxCount; i++) { BoxList[i] = long.Parse(Reader.ReadLine()); Total+=BoxList[i]; } long ans = this.GetAns(0, (Total + Temoti) / boxCount); Console.WriteLine(ans); } private long GetAns(long min, long max) { if(max - min <= 1) { return Math.Min(GetCount(min), GetCount(max)); } long q2 = (max + min) / 2; long q1 = (q2 + min) / 2; long q3 = (q2 + max) / 2; long minVal = this.GetCount(min); long maxVal = this.GetCount(max); long q1Val = this.GetCount(q1); long q2Val = this.GetCount(q2); long q3Val = this.GetCount(q3); long minCount = new long[] {minVal, maxVal, q1Val, q2Val, q3Val}.Min(a=>a); if(minVal == minCount) { return this.GetAns(min, q1); } else if(q1Val == minCount) { return this.GetAns(min, q2); } else if(q2Val == minCount) { return this.GetAns(q1, q3); } else if(q3Val == minCount) { return this.GetAns(q2,max); } else { return this.GetAns(q3, max); } } private long GetCount(long target) { if(target * BoxList.Length > Temoti + Total) { return long.MaxValue; } long ans = 0; foreach (long candy in BoxList) { ans += Math.Abs(candy - target); } return ans; } private long[] BoxList; private long Temoti; private long Total; public class Reader { public static bool IsDebug = true; private static String PlainInput = @" 169219876 10 135 24876433 24876476 24876781 24876007 2000 24875934 24876438 24876122 24876474 "; private static System.IO.StringReader Sr = null; public static string ReadLine() { if (IsDebug) { if (Sr == null) { Sr = new System.IO.StringReader(PlainInput.Trim()); } return Sr.ReadLine(); } else { return Console.ReadLine(); } } } static void Main() { Program prg = new Program(); prg.Proc(); } }