結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー |
![]() |
提出日時 | 2017-07-16 00:27:32 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 2,465 bytes |
コンパイル時間 | 961 ms |
コンパイル使用メモリ | 115,408 KB |
実行使用メモリ | 32,776 KB |
最終ジャッジ日時 | 2024-10-08 02:44:16 |
合計ジャッジ時間 | 3,677 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
コンパイルメッセージ
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.Specialized; using System.Linq; class Solution { static long GetBestValue(long v, long[] array) { // 2分探索で-vに最も近いものを探す int minRange = 0; int maxRange = array.Count() - 1; while (minRange != maxRange) { var center = (minRange + maxRange) / 2; if (array[center] < -v) { minRange = center + 1; } else { maxRange = center; } } // array[minRange]は-vか-vを超える最小の値 var best = Math.Abs(v + array[minRange]); if (minRange > 0) { var t = Math.Abs(v + array[minRange - 1]); best = Math.Min(best, t); } return best; } static void Main() { var n = int.Parse(Console.ReadLine()); var a = new long[n]; var b = new long[n]; for (int i = 0; i < n; i++) { var vals = Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); a[i] = vals[0]; b[i] = vals[1]; } if (n == 1) { Console.WriteLine($"{Math.Min(a[0], b[0])}"); return; } // 半分全列挙 var halfLength = new int[] { n / 2, n - (n / 2) }; var halfPatterns = halfLength.Select(i => 1 << i).ToArray(); var half = halfPatterns.Select(i => new long[i]).ToArray(); for (int i = 0; i < 2; i++) { int start = i * halfLength[0]; for (int pattern = 0; pattern < halfPatterns[i]; pattern++) { var bits = new BitVector32(pattern); for (int j = 0; j < halfLength[i]; j++) { if (bits[1 << j]) { half[i][pattern] += a[start + j]; } else { half[i][pattern] -= b[start + j]; } } } } half[1] = half[1].OrderBy(i => i).ToArray(); var best = long.MaxValue; for (int pattern = 0; pattern < halfPatterns[0]; pattern++) { var v = half[0][pattern]; var t = GetBestValue(v, half[1]); best = Math.Min(best, t); } Console.WriteLine(best); } }