题目描述
blablabla
样例
blablabla
算法1
(二分) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,l;
int a[100010];
bool cmp(int x,int y)
{
return x>y;
}
bool check(int x)//唯一目的就是看这个x作为最终答案h是否合理
{
int b=0,c=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=x) b++;//找a[i]>=h
if(x-a[i]==1) c++;//找比h恰好小1的a[i],因为每一个数只能加一次1,故只有a[i]==h-1时才有可能通过后续操作达到h
}
//又因为最多只能加l次,故能新增加为h的论文数量为min(l,c);
return b+min(l,c)>=x;//根据题意,至少有h篇论文的引用次数不少于h
}
//二分答案:h的取值具有二段性:若h合理,则对于任意h0<=h,必然合理
int main()
{
cin>>n>>l;
for(int i=1;i<=n;i++) cin>>a[i];
//sort(a+1,a+1+n,cmp);
int l=0,r=100001;
//二分h
while(l+1<r)
{
int mid=l+r>>1;
if(check(mid)) l=mid;
else r=mid;
}
cout<<l;
return 0;
}
算法2
(贪心找规律) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n,l;
int a[100010];
bool cmp(int x,int y)
{
return x>y;
}
//二分答案:h的取值具有二段性:若h合理,则对于任意h0<=h,必然合理
int main()
{
cin>>n>>l;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+1+n,cmp);//降序排序,前面的论文更可能符合要求
int h=0;
for(int i=1;i<=n;i++)
{
if(a[i]>=i) h=i;//记录当前的h,结果会取最后覆盖的那个h,此时的h最大,为当前的答案
else break;//找到了第一个不合理的数,直接退出
}
//接下来要进行l次操作,可以给每一个论文引用次数加1,但一篇论文最多只能加一次
//所以由此可知,h最多能增加为h+1。因为由上面for循环的性质,可得a[h]>=h且a[h+1]<h+1。若h增加为h+1,意味着有h+1篇论文的引用次数至少为h+1.
//假设h能取到h+2,则由a[h+1]<h+1,a[h+1]即后面的数是不可能加到h+2的(因为每个数最多只能加1次)。也就是说引用次数可能>=h+2的论文最多有h篇。
//显然取不到这样的h。故最终答案不是h就是h+1。
//先特判一下a[h+1]是否<h,若成立,则h不可能取到h+1(因为它以及后面的数都不肯加到h+1)
if(a[h+1]<h)
{
cout<<h<<endl;
return 0;
}
//若a[h+1]==h,则看a[1~h+1]中等于h的数的数量cnt,因为只有它们可能增加为h+1
int cnt=0;
for(int i=h+1;i>=1;i--)
{
if(a[i]==h) cnt++;
else break;
}
//看是否能增加这cnt个论文
if(l>=cnt) cout<<h+1<<endl;//可以,那么h指数可以增加
else cout<<h<<endl;//不够,h指数仍为h
return 0;
}