CodeChef Chef and A Large Permutation

題目鏈接:http://www.codechef.com/problems/CLPERM/

題意

解法

將0放到數組開始n+1放到數組末尾
首先對b[i]排序,假設前i個數都可選,而且構成的最大的數字為max,當前b[now]不可用
如果max<b[now]那麼最大隻能構成max了
否則令L=b[now]+1和R=b[now+1]-1
那麼最大可以夠成的和數字變為max=max+(R+L)*(R-L+1)/2
最後只需要判斷一下max的奇偶性即可

class CLPERM {
    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int n=in.nextInt();
        int k=in.nextInt();
        long[] b=new long[k+2];
        b[0]=0;
        b[k+1]=n+1;
        for(int i=1;i<=k;i++) b[i]=in.nextLong();
        Arrays.sort(b);
        long max=0;
        for(int i=0;i<=k;i++) {
            if(max<b[i]) {
                break;
            }else {
                long l=b[i]+1;
                long r=b[i+1]-1;
                max+=(l+r)*(r-l+1)/2;
            }
        }
        if(max%2==1) out.println("Mom");
        else out.println("Chef");
    }
}