TopCoder SRM 588: GUMIAndSongsDiv1

問題文

tone が最大の歌と最小の歌を固定して、あとはその範囲内の歌の中から duration が低いものを貪欲に選んでいけばよい。
このとき、「tone が最大の歌と最小の歌」を絶対選ぶようにしなくても、選ばれなかった時点で内側の範囲のほうがよりよい解が得られるので、とくに気にする必要はない。

public class GUMIAndSongsDiv1 {
    public int maxSongs(int[] duration, int[] tone, int T) {
        int N = duration.Length;
        var songs = Enumerable.Range(0, N)
            .Select(i => new { duration = duration[i], tone = tone[i] })
            .OrderBy(s => s.tone).ToArray();

        int ans = 0;

        for (int i = 0; i < N; i++)
            for (int j = i; j < N; j++) {
                var sub = songs.Where((s, index) => i <= index && index <= j).ToArray();
                if (sub.Length == 1) {
                    if (sub[0].duration <= T) {
                        ans = Math.Max(ans, 1);
                    }
                } else {
                    long total = Math.Abs(sub.First().tone - sub.Last().tone);
                    int num = 0;
                    foreach (var song in sub.OrderBy(s => s.duration)) {
                        total += song.duration;
                        if (total <= T) {
                            num++;
                        } else break;
                    }
                    ans = Math.Max(ans, num);
                }
            }
        return ans;
    }
}