NC19916 [CQOI2010]扑克牌
NC19916 [CQOI2010]扑克牌
题目
题目描述
你有n种牌,第i种牌的数目为 \(c_i\) 。另外有一种特殊的牌:joker,它的数目是m。你可以用每种牌各一张来组成一套牌,也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如,当n=3时,一共有4种合法的套牌:{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和 \(c_i\) ,你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里(可以有牌不使用)。
输入描述
第一行包含两个整数n, m,即牌的种数和joker的个数。
第二行包含n个整数 \(c_i\) ,即每种牌的张数。
输出描述
输出仅一个整数,即最多组成的套牌数目。
示例1
输入
3 4
1 2 3
输出
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< = c_i < = 200\)
\(100\%\) 的数据满足:\(2< = n < = 50, 0 < = m, c_i <= 500,000,000\) 。
题解
思路
知识点:二分。
答案符合单调性,二分答案,判断可行性。
只要 \(\sum max(mid-c_i,0) <= mid \ \and \ \sum max(mid-c_i,0) <= m\) ,表示缺的牌总和要小于等于套牌总数,否则由于鸽巢原理一定存在一套牌有两个 J ;缺的牌总和要小于等于 J 总数,否则无法补齐。
记得 \(sum\) 开 \(long \ long\) 。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
int c[57];
bool check(int mid) {
long long sum = 0;
for (int i = 0;i < n;i++) sum += max(mid - c[i], 0);
return sum <= mid && sum <= m;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m;
for (int i = 0;i < n;i++) cin >> c[i];
int l = 0, r = 1e9;///理论最大值
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
cout << r << '\n';
return 0;
}
最新文章
- Jquery-UI使用
- c++多重继承
- Spark DAGSheduler生成Stage过程分析实验
- Lua使用心得(2)
- CCF真题之画图
- 计时器Chronometer和时钟(AnalogClock和DigitalClock)
- Python之路【第十七篇】:Django【进阶篇】
- Speech Module
- 【最大流,二分图匹配】【hdu2063】【过山车】
- 用 Eclipse 下载 Git 仓库中代码
- cocos2d-x3.0 解释具体的新的物理引擎setCategoryBitmask()、setContactTestBitmask()、setCollisionBitmask()
- Got fatal error 1236 from master when reading data from binary log: &#39;Could not find first log file name in binary log index file&#39;系列一:
- jquery位置问题
- mpvue使用scroll-view实现图片横向滑动
- 【Java面试题】36 List、Map、Set三个接口,存取元素时,各有什么特点?
- Golang基本结构之练习(day2)
- tomcat服务器开启gzip功能的方法
- scala Wordcount
- DB2 编目并访问远程数据库
- PHP对接QQ互联,超级详细!!!