solution
这数据范围是故意误导人的叭。。。
显然答案具有单调性,如果可以组成n副,那么一定能组成n-1副啊(这也太废话了叭)。
然后很容易想到要二分答案。假设现在二分了一个答案x。考虑如何去判断是否可行。
如果不考虑每副牌最多只有一个joker的话,那只要看一下是不是满足就行了。
然后考虑每副牌最多只有一个joker。我们要组成x副牌,每副牌最多只有一个joker,所以最多安放x个joker。而且如果安放了x个joker一定有办法让他们不在同一副牌里。考虑每个joker代替的牌种类都不相同的情况,我们只要让第一个joker出现在第一幅牌里,第二个joker出现在第二副牌里....。如果有joker代替了同一种牌,显然这一种牌不会出现在同一副牌里。所以也是可以安放的。
所以就二分一个x,计算一下还要多少个joker才能使每副牌的数量都。然后判断这个数量是不是就行了
code
/* * @Author: wxyww * @Date: 2020-06-03 20:28:57 * @Last Modified time: 2020-06-03 20:35:44 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> #include<cmath> using namespace std; typedef long long ll; const int N = 110; #define int ll ll read() { ll x = 0,f = 1;char c = getchar(); while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar(); } while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); } return x * f; } int a[N],n,m; bool check(int x) { int t = min(m,x); for(int i = 1;i <= n;++i) { t -= max(0ll,x - a[i]); } return t >= 0; } signed main() { n = read(),m = read(); for(int i = 1;i <= n;++i) a[i] = read(); int l = 1,r = 1e9,ans = 0; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) ans = mid,l = mid + 1; else r = mid - 1; } cout<<ans; return 0; }