自己先按从小到大排序试了一遍,会有几个数据集超时
#include <iostream>
#include <cstring>
#include <algorithm>
#include<cstdio>
using namespace std;
const int N = 100010;
int a[N];
int n, l;
int res;
int main()
{
scanf("%d%d",&n,&l);
for(int i =1;i<=n;i++)
scanf("%d",&a[i]);
sort(a + 1, a + n+1);//注意排序索引!!!
for (int i = 1, j = n; i <= n; i++) {
j = n;
while (j && a[j] >= i)j--;
if (a[n - i + 1] >= i - 1 && i - n + j <= l)
res = i;
}
cout << res << endl;
return 0;
}
考虑数据集很大的时候,可能会多次跑while循环,反过来排序会更方便
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int a[N];
int n,l;
int res;
int main()
{
scanf("%d%d",&n,&l);
for(int i =1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());
for (int i = 1,j=n; i <= n; i ++ ){
while(j&&a[j]<i)j--;
if(a[i]>=i-1&&i-j<=l)
res=i;
else break;
}
cout<<res<<endl;
return 0;
}