[CQOI2010]扑克牌 题解

思路:二分
二分出x的值，然后看看能不能凑出x副牌
精髓就是写一个check函数 来检查下是否可以凑出
如果c[i]的值大于等于x的值，说明每一副牌都可以有一张此扑克牌
如果c[i]的值小于x的值，说明不够用，需要用J牌来替代此牌 就需要x-c[i]张J
遍历完之后，如果需要J牌的数量ans>x,这样的话就一定有一副牌有两个J不符合题意
如果ans>m,这样手里的J就不够用了，也无法凑出x套牌。

import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static int n=0;
    public static int m=0;
    public static long c[];
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = (int)in.nval;
        in.nextToken();
        m = (int)in.nval;
        c = new long[n];
        for(int i=0;i<n;i++)
        {
            in.nextToken();
            c[i] = (long)in.nval;
        }
        int l=0,r=1000000009,mid =(l+r)/2;
            while(l<=r)
            {
               mid =(l+r)/2;
                if(check(mid)==true)
                {
                    l = mid+1;
                }
                else{
                    r = mid-1;
                }
            }
            out.println(l-1);

        out.flush();
    }
    public static boolean check(long x)
    {
        long ans=0;
       for(int i=0;i<n;i++)
       {
           if(c[i]<x)
               ans+=x-c[i];
       }
        if(ans>m||ans>x)
            return false;
        else
            return true;
    }
                  }