Hatena::Grouptopcoder

yambe2002の日記

 | 

2016-03-29

SRM686 Div2 Mid: SegmentsAndPoints

21:37

直線上に点がいくつかある。それと同じ数だけ、直線上の範囲の組み合わせも与えられる。

点:p[]

範囲:l、r

すべての点が、どれかの範囲とペアにすることが可能か求めよ。

点の小さい方からループ:

  点の位置を含む範囲を抽出

  該当範囲のr[]が最小のものを取り出す

を繰り返すだけ。

public class SegmentsAndPoints {
    public string isPossible(int[] p, int[] l, int[] r) {
        var list = new List<Tuple<int, int>>();

        for (int i = 0; i < l.Length; i++)
        {
            var pair = new Tuple<int, int>(l[i], r[i]);
            list.Add(pair);
        }

        p = p.OrderBy(v => v).ToArray();

        for (int i = 0; i < p.Length; i++)
        {
            var tgt = list.Where(v => v.Item1 <= p[i] && v.Item2 >= p[i]).OrderBy(w => w.Item2).FirstOrDefault();
            if (tgt == null) return "Impossible";

            list.Remove(tgt);
        }

        return "Possible";
    }
}

SRM686結果:○○-

なんとギリギリでDiv1に上がってしまった。Hard解いたことないのに・・・。

 |