TopCoder SRM 659 Div1 ApplesAndOrangesEasy

題目鏈接:http://community.topcoder.com/stat?c=problem_statement&pm=13791&rd=16462

題意

一個人有一些N個水果,不是apple就是orange,這個人在每一個時刻吃一個水果,並且每個時刻滿足
該時刻最後K個水果中蘋果的數量不超過K/2,給定info[]表示info[i]位置的水果是蘋果
求最多有多少個蘋果

解法

貪心暴力判斷
對於未知的位置i假設該位置是蘋果然後判斷是否滿足條件
不斷枚舉位置i判斷是否可行即可

public class ApplesAndOrangesEasy {
    public int maximumApples(int N, int K, int[] info) {
        int half=K/2;
        boolean is[]=new boolean[N];
        for(int i:info) {
            is[i-1]=true;
        }
        for(int i=0;i<N;i++) {
            if(is[i]) continue;
            is[i]=true;
            int sum=0;
            for(int j=0;j<K;j++) {
                sum+=is[j]? 1:0;
            }
            boolean can=(sum<=half);
            for(int j=K;j<N;j++) {
                sum-=is[j-K]? 1:0;
                sum+=is[j]? 1:0;
                if(sum>half) {
                    can=false;
                }
            }
            if(!can) {
                is[i]=false;
            }
        }
        int res=0;
        for(int i=0;i<N;i++) {
            res+=is[i]? 1:0;
        }
        return res;
    }
}