[Cqoi2010]扑克牌
Posted on 2015年1月13日 19:291 2 3 4 5 6 7 8 9 10 | /****************************************\* Author : ztx* Title : [Cqoi2010]扑克牌* ALG : 二分* CMT :* 首先二分答案,设组成的套数为M,* 在判断是否成立时 , 枚举每一个c , 若ci<M , 则用joker补,* 使用的joker必须要小于等于min(m,M)* Time :\****************************************/ |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | /****************************************\* Author : ztx* Title : [Cqoi2010]扑克牌* ALG : 二分* CMT :* 首先二分答案,设组成的套数为M,* 在判断是否成立时 , 枚举每一个c , 若ci<M , 则用joker补,* 使用的joker必须要小于等于min(m,M)* Time :\****************************************/#include <cstdio>#define maxn 55LL#define maxc 1000000000LLint n , m , i ;int c[maxn] ;int cnt ;inline bool Could(int M) { cnt = 0 ; for (i = 1 ; i <= n ; i ++ ) { if (c[i] < M) cnt += M-c[i] ; if (cnt > M || cnt > m) return false ; } return true ;}int L , R , M ;inline int Bsearch() { L = 0 , R = maxc+1 ; while (R-L > 1) { /* [L , R) */ M = L+(R-L)/2 ; if (Could(M)) L = M ; else R = M ; } return L ;}int main() {// #define READ #ifdef READ freopen(".in" ,"r",stdin ) ; freopen(".out","w",stdout) ; #endif scanf("%d%d", &n , &m ) ; for (i = 1 ; i <= n ; i ++ ) scanf("%d", &c[i] ) ; printf("%d\n", Bsearch() ) ; #ifdef READ fclose(stdin) ; fclose(stdout) ; #else getchar() ; getchar() ; #endif return 0 ;} |