二分答案 扑克牌

 1 program hehe;
 2 var
 3  n,m,i,j:longint;
 4  c:array[0..50] of longint;
 5
 6   function min(a,b:longint):longint;
 7   begin
 8    if a>b then exit(b);
 9    exit(a);
10   end;
11
12   function ok(a:longint):boolean;
13   var
14    f,t:longint;
15   begin
16    t:=min(a,m);
17    for f:=1 to n do
18    begin
19     if c[f]<a then
20     t:=t-a+c[f];
21     if t<0 then exit(false);
22    end;
23    exit(true);
24   end;
25
26   function ef(l,r:longint):longint;
27   var
28    mid:longint;
29   begin
30    if l=r then exit(l);
31    mid:=(l+r)>>1;
32    if ok(mid+1) then
33    exit(ef(mid+1,r))
34    else exit(ef(l,mid));
35   end;
36
37 begin
38  readln(n,m);
39  for i:=1 to n do read(c[i]);
40  writeln(ef(1,maxlongint-1));
41 end.

1816: [Cqoi2010]扑克牌

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 1473  Solved: 566
[Submit][Status][Discuss]

Description

你有n种牌,第i种牌的数目为ci。另外有一种特殊的牌:joker,它的数目是m。你可以用每种牌各一张来组成一套牌,也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如,当n=3时,一共有4种合法的套牌:{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。

Input

第一行包含两个整数n, m,即牌的种数和joker的个数。第二行包含n个整数ci,即每种牌的张数。

Output

输出仅一个整数,即最多组成的套牌数目。

Sample Input

3 4
1 2 3

Sample Output

3

样例解释
输入数据表明:一共有1个1,2个2,3个3,4个joker。最多可以组成三副套牌:{1,J,3}, {J,2,3}, {J,2,3},joker还剩一个,其余牌全部用完。

数据范围
50%的数据满足:2 < = n < = 5, 0 < = m < = 10^ 6, 0< = ci < = 200
100%的数据满足:2 < = n < = 50, 0 < = m, ci < = 500,000,000。

HINT

Source

[Submit][Status][Discuss]

时间: 06-14

二分答案 扑克牌的相关文章

BZOJ 1816: [Cqoi2010]扑克牌( 二分答案 )

二分答案.. 一开始二分的初始右边界太小了然后WA,最后一气之下把它改成了INF... ------------------------------------------------------------------------ #include<cstdio> #include<cstring> #include<algorithm> #include<iostream> #define rep( i , n ) for( int i = 0 ; i

bzoj1816: [Cqoi2010]扑克牌(二分答案判断)

1816: [Cqoi2010]扑克牌 题目:传送门 题解: 被一道毒瘤题搞残了...弃了坑来刷刷水题 一开始还想复杂了...结果发现二分水过: 二分答案...然后check一下,joker肯定尽量用mid次,那么哪种牌不够就补(因为每次只能补一种,所以如果次数用完就return false) 代码: 1 #include<cstdio> 2 #include<cstring> 3 #include<cstdlib> 4 #include<cmath> 5

[BZOJ 1816][Cqoi2010]扑克牌(二分答案)

题目:http://www.lydsy.com/JudgeOnline/problem.php?id=1816 分析: 我先以为是道水题,但是要注意的是每套牌中Joker只能用1张的,所以就出现了可能目前每种牌的剩余牌数都够,但不一定不用Joker,然后就短路了…… 看了hzwer的blog顿时茅塞顿开,原来是二分…… 二分答案x,然后判定 判定的方法:注意每套牌顶多只有一个Joker,所以对于答案x,能用的Joker的最大数量是T=Min(x,m),然后枚举每种牌,将每种牌相对于答案x差的个数

[BZOJ 1816] [Cqoi2010] 扑克牌 【二分答案】

题目链接:BZOJ - 1816 题目分析 答案具有可以二分的性质,所以可以二分答案. 验证一个答案 x 是否可行,就累加一下各种牌相对于 x 还缺少的量,如果总和超过了 x 或 m ,就不可行. 因为,当使用的joker小于等于 x 时,才可以通过合适地安排顺序使得每组牌中至多有一张 joker . 代码 #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio>

Codeforces 772A Voltage Keepsake - 二分答案

You have n devices that you want to use simultaneously. The i-th device uses ai units of power per second. This usage is continuous. That is, in λ seconds, the device will use λ·ai units of power. The i-th device currently has bi units of power store

HDU3081Marriage Match II(二分答案+并查集+最大流SAP)经典

Marriage Match II Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2507    Accepted Submission(s): 856 Problem Description Presumably, you all have known the question of stable marriage match. A

Codeforce 371C Hamburgers (二分答案)

题目链接 Hamburgers 二分答案,贪心判断即可. 1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define REP(i,n) for(int i(0); i < (n); ++i) 6 #define LL long long 7 8 char str[1010]; 9 LL len; 10 LL b, c, s, nb, nc, ns, pb, pc, ps; 11 LL money; 12 13 bool

POJ 3080 Blue Jeans(后缀数组+二分答案)

[题目链接] http://poj.org/problem?id=3080 [题目大意] 求k个串的最长公共子串,如果存在多个则输出字典序最小,如果长度小于3则判断查找失败. [题解] 将所有字符串通过拼接符拼成一个串,做一遍后缀数组,二分答案,对于二分所得值,将h数组大于这个值的相邻元素分为一组,判断组内元素是否覆盖全字典,是则答案成立,对于答案扫描sa,输出第一个扫描到的子串即可. [代码] #include <cstdio> #include <cstring> #inclu

【二分答案+智障的字符串hash】BZOJ2946-[Poi2000]公共串(Ranklist倒一达成!!!!!)【含hash知识点】

[题目大意] 给出几个由小写字母构成的单词,求它们最长的公共子串的长度. [字符串hash的小笔记] hash[i]=(hash[i-1]*p+idx(s[i]))%mod,idx为映射值,一般a..z映射1..26: 习惯上,p取一个6到8位的素数即可,mod一般取大素数 1e9+7(1000000007)或1e9+9(1000000009). hash[i]=(hash[i-1]*p+idx(s[i]))%mod 表示第 i 个前缀的hash值,是一个hash的前缀和,那么,要求S[l…r]