分析
本题的意思 是让 给出的数组,是否能拿出h个大于等于h的数,有一个附加条件,可以用给l个数加上一,以达到前边的那个条件, 也就是可以拿至多 l个 h-1 数凑进去。
这样的话,想要满足题目的要求有三种情况:
1:
不需要用h-1的数来凑
2:
需要用h-1的数来凑,且能凑够
3:
所有h-1的数凑上也不够
我们把这个数组c从大到小排个序 吧
现在我们再次来看上边三种情况:
对于第一种情况,c[i]>i 表示 i为h可满足
对于第二种情况,只要在i左边的 h-1的个数小于等于l,也可满足
对于第三章情况,c[i]< h-1 ,没救了,肯定不能用
从左到右,从大到小遍历一下,按照上边的三种情况进行处理,取到最大的i即可(i从0开始就是i+1)
C++ 代码
#include<iostream>
#include<vector>
#include<unordered_map>
#include<algorithm>
using namespace std;
const int N = 1e6 + 5;
#define endl '\n';
#define int long long
void fast() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
typedef pair<int, int> PII;
typedef pair<int, int> PIS;
int a[N] = {1, 2, 3, 100, 100, 100, 100, 101, 102, 103};
int n, l;
int h[N];
void solve() {
cin >> n >> l;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
sort(a, a + n, greater<int>());
int ans = 0;
for (int i = 0; i < n; ++i) {
int hh = i + 1;
h[a[i]]++;
if (a[i] >= hh)ans = hh;
else if (a[i] == i) {
if (l >= h[i])
ans = hh;
else {
break;
}
} else {
break;
}
}
cout << ans;
}
signed main() {
solve();
return 0;
}
赞