TopCoder SRM 659 Div1 Easy: ApplesAndOrangesEasy（貪欲法）

解法

前からフルーツを見ていって、そのフルーツからKの範囲内にリンゴがK/2個以内なら、そのフルーツをリンゴにしても良い。

コード

public class ApplesAndOrangesEasy {

    public int maximumApples(int N, int K, int[] info) {
	boolean[] isApple = new boolean[N];
	for (int i = 0; i < info.length; i++) {
	    isApple[info[i] - 1] = true;
	}

	final int canBeContain = K / 2;

	for (int i = 0; i < N; i++) {
	    boolean containable = true;
	    for (int start = Math.max(0, i - K + 1); start <= i; start++) {
		int cnt = 0;
		for (int j = 0; j < K && start + j < N; j++) {
		    if (isApple[start + j]) {
			cnt++;
		    }
		    if (cnt == canBeContain) {
			containable = false;
			break;
		    }
		}
		if (!containable) {
		    break;
		}
	    }
	    if (containable) {
		isApple[i] = true;
	    }
	}

	int ans = 0;
	for (int i = 0; i < isApple.length; i++) {
	    if (isApple[i]) {
		ans++;
	    }
	}
	return ans;
    }

}