网站打开是别人的,网站建设新手,建筑公司资质等级,用php制作一个个人信息网站链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
题目描述
你有n种牌#xff0c;第i种牌的数目为ci。另外有一种特殊的牌#xff1a;joker#xff0c;它的数目是m。你可以用每种牌各一张来组成一套牌#xff0c;也可以用一张joker和除了某…链接登录—专业IT笔试面试备考平台_牛客网 来源牛客网
题目描述
你有n种牌第i种牌的数目为ci。另外有一种特殊的牌joker它的数目是m。你可以用每种牌各一张来组成一套牌也可以用一张joker和除了某一种牌以外的其他牌各一张组成1套牌。比如当n3时一共有4种合法的套牌{1,2,3}, {J,2,3}, {1,J,3}, {1,2,J}。 给出n, m和ci你的任务是组成尽量多的套牌。每张牌最多只能用在一副套牌里可以有牌不使用。
输入描述: 第一行包含两个整数n, m即牌的种数和joker的个数。
第二行包含n个整数ci即每种牌的张数。
输出描述:
输出仅一个整数即最多组成的套牌数目。
示例1
输入
复制3 4 1 2 3
3 4
1 2 3
输出
复制3
3
说明
样例解释
输入数据表明一共有1个12个23个34个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。 分析
二分求值数据有点坑除了常规牌还要考虑joker所以r1e9 #includebits/stdc.h
typedef long long ll;
using namespace std;
void solve()
{ll n,m;cinnm;vectorll p(n,0);for(ll i0;in;i){cinp[i];}auto check[](ll mid){ll sums0;for(ll i0;in;i){if(p[i]mid)//如果某个牌小于套牌数那么说明需要joker牌sumsmid-p[i];//需要joker数}if(sumsm||sumsmid)return false;//如果需要的joker大于现在有的说明不满足或者需要的joker数大于套牌数说明一套牌有多个jokerelse return true;};ll l1,r5000000009;ll md0;while(lr){ll midl(r-l)/2;if(check(mid)){mdmid;lmid1;}else rmid-1;}coutmd\n;
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t1;while(t--)solve();return 0;
}
