ABC 023 D 射撃王

2015/05/13 (Wed) ABC AtCoder 二分探索

問題

問題文

方針

風船が到達できる上限を決めて，その高さに達しないような順番で風船を撃墜できるか？という判定関数をつくる． これは，到達するまでの時間を求めて昇順に撃墜していけば確かめられる．

この関数は 0 を渡すと必ず false を返し，高さを上昇させていくとある一点から true に切り替わる． したがって二分探索が使える．

実装

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
class Solver
{
    static int N;
    static long[] H, S;
    static void Main()
    {
        N = int.Parse(Console.ReadLine());
        H = new long[N];
        S = new long[N];
        for (int i = 0; i < N; i++)
        {
            string[] s = Console.ReadLine().Split(' ');
            H[i] = long.Parse(s[0]);
            S[i] = long.Parse(s[1]);
        }
        long ub = 0;
        for (int i = 0; i < N; i++)
        {
            ub = Math.Max(ub, H[i] + S[i] * (N - 1)) + 10;
        }
        long lb = 0;
        while(lb + 1 < ub)
        {
            long mid = (ub + lb) / 2;
            if (chk(mid)) ub = mid;
            else lb = mid;
        }
        Console.WriteLine(ub);
    }
    static bool chk(long lim)
    {
        long[] rem = new long[N];
        for (int i = 0; i < N; i++)
        {
            if (lim - H[i] < 0) return false;
            rem[i] = (lim - H[i]) / S[i];
        }
        Array.Sort(rem);
        for (int i = 0; i < N; i++)
        {
            if (rem[i] < i) return false;
        }
        return true;
    }
}