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;
}
}
コメント
- 非自明かつ実装アイデアが思いつかなかった
