P7557 [USACO21OPEN] Acowdemia S 题解

· · 题解

前言

我有一个不用二分，极其简单的方法。

题意

给一个序列 a，你可以操作 K 次，每次将至多 L 个数字 +1 ，求最大的 h 指数，h 指数为有至少 h 个 a_i \leq h。如 1 1 2 2 3 这里最大的 h 指数为 2。因为有 3 个大于等于的数，分别为 2 2 3，而且 3>2，所以成立。而 3 不行因为只有 1 个大于等于的数 3，而且 1<3，所以 h 为 3 不行。

分析

首先，我们观察题意。

我们不难发现，题目想我们这么做：

  1. 当 \ge h 的数的个数不 \ge h 个时。
  2. 先算出在序列中小于 h 的同时最大的 h-o 个数（o 为大于 h 的数的个数）。
  3. 将这 h-o 个数的数字大小加起来，叫做 sum。
  4. 算出 h \times (h-o) 即所需大小的总和减 sum 的值，叫做 sumi。
  5. 最后比较 sumi 与 k，l 大小关系，看一下操作数量够不够。

那么如何用最短的时间求最大的 h 呢?

  1. 我们可以先 sort 排序数列保证有单调性。（从小到大）
  2. 后算出前缀和。
  3. 从小到大枚举 h 指数，当 a_i\ge i 时代表这个大小的 h 合法，相反则代表需要进行操作使这 h-o 个数加上 sumi。o 在第一次 a_i<i 时使其等于 i。而后每次向前遍历 o 直到 a_o>i。注意这里的 o 无需更改，因为 sort 后的数列有单调性。
  4. 最后判断，当 k 要大于等于 h-o 中的最小值，且 \min(l,n)\times k\ge h\times(h-o)。如果成立更新 ans=i 即 h 指数。最最后输出 ans 即可。

于是，我们不难调出如下代码。但是，需要注意的是！要特判 o 不为 0 即当我们查找大于当前的 h 的数字的个数（向前遍历）,且要写当 h 指数不变的情况。一般就是 l=0 或是 k=0 即 k 乘上 l 太小了的情况，所以要每次记录更新 ans 即最大的 h 指数。

时间复杂度及其证明

时间复杂度：O(n \log n)

证明：用到了 sort 所以极限情况是 O(n \log n)，遍历 h 和前缀和只用 O(n)，求 o 时每次循环 o 的大小是不定义循环初始值的，一直遍历下去，所以只用 O(n)。

本人代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,a[2000005],x,ans,k,l,qzh[200005],m,o;
bool cmp(ll ai,ll bi){
    return ai>bi;
}
int main(){
    cin>>n>>k>>l;
    if(l>n)l=n;//特判l大于n时则多余的为无意义要舍去
    m=k*l;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n,cmp);//排序数列保证其有单调性（从小到大）
    for(int i=1;i<=n;i++){
        qzh[i]=qzh[i-1]+a[i];
    }//求前缀和
    for(int i=1;i<=n;i++){//从小到大枚举h
        if(a[i]<i){
            for(;a[o]<i&&o;o--){} //求大于h的数有哪些
            if(i*(i-o)-qzh[i]+qzh[o]<=m&&i-a[i]<=k){//判断操作是否够
                ans=i;//更新ans即最大的h指数。
            }
        }
        else {
            ans=i;//更新ans在无需操作时最大的h指数。
            o=i;//记录>h的个数
        }
    } 
    cout<<ans;
    return 0;
}