SRM631D1Med CatsOnTheLineDiv1

難しい

問題概要(原文)

数直線の $N$ 箇所に猫がいる. 左から $i$ 番目には位置 $x_i$ に $k_i$ 匹猫がいる.

単位時間に $1$ だけ猫は移動できる(しなくてもよい).時刻 $t$ が経過したあと,猫が $2$ 匹以上いる位置の数を最小化したい.

考察

戦略として平べったく寄せるか,まとめて重ねるか,が重要である. それ以外のケースはどうやっても損をする.

よってそのようなgreedyをやる.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class CatsOnTheLineDiv1
{
    public int getNumber(int[] pos, int[] count, int time)
    {
        Array.Sort(pos, count);
        var ans = 0;
        var p = int.MinValue;
        var r = int.MinValue;
        var n = pos.Length;
        for (int i = 0; i < n; i++)
        {
            if (r >= pos[i] - time) continue;
            var q = Math.Max(p + 1, pos[i] - time) - 1 + count[i];
            if (q > pos[i] + time)
            {
                r = pos[i] + time;
                ans++;
            }
            else p = q;
        }
        return ans;
    }
}

コメント

  • 非自明かつ実装アイデアが思いつかなかった