AcWing 3745. 牛的学术圈 I——单 log 与线性两种复杂度做法

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 3745. 牛的学术圈 I——单 log 与线性两种复杂度做法原题链接简单

作者：

Conan15 , 2021-12-25 18:02:24 , 所有人可见 , 阅读 8426

123

6

宣传一下 $\Huge\color{green}{春季每日一题题解}$

老久之前写的题解了，最近发现点赞数突然增加，~~原来又是每日一题造的孽~~。

之前写的过于粗糙，现在（2024.3.5）进行略微修改。

先二分，再 sort，随后给每个 $\leq h$ 的数加 $1$ ，直到 $l==0$ ，再二分一次求 ans。
但是在 USACO 过不了，因为要开 long long……
这里感谢大神们给出的提示，大家一定要注意这些溢出的问题。
另外请注意二分的写法，错误写法容易死循环，具体可以参考这里。

时间复杂度 $O(N \log N)$ 。

#include <bits/stdc++.h>
using namespace std;
int n, k, c[100010];
int check(int x) { //求h是否成立 
    int ans = 0;
    for (int i = 1;i <= n; i++) if (c[i] >= x) ans++;
    return ans >= x;
}
int main() {
    scanf("%d%d", &n, &k);
    int l = 100010, r = 0;
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]), l = min(l, c[i]), r = max(r, c[i]);
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (!check(mid)) r = mid - 1;
        else l = mid;
    }
    sort(c + 1, c + 1 + n);
    for (int i = n;i > 0; i--) {
        if (k == 0) break;
        if (c[i] <= l) c[i]++, k--; 
    }
    l = 0, r = 100000;
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (!check(mid)) r = mid - 1;
        else l = mid;
    }
    printf("%d", l);
    return 0;
}

接着是我的第二种解法，就是统计一下每个引用次数的cnt（出现次数），然后就 for循环一遍 0~n。
这里的 for 循环 ans 只是到了 n，是因为：

$h$ 指数等于使得研究员有至少 $h$ 篇引用次数不少于 $h$ 的论文的最大整数 $h$ 。

显然 $h$ 一定不会超过总篇数 $n$ 。
那这样就可以统计了，代码实现也挺简单。

另外感谢 @JcWing 大佬指出的问题，这里的 map 确实是多余的，可以修改为数组。
这样复杂度还能省掉一个 log，~~千万不要问我为什么我几年前那么弱智~~。
~~但是我懒得写了，大家应该都知道怎么改吧？~~

时间复杂度 $O(N)$ ，~~没错下面是带 log 大常数的做法~~。

#include <bits/stdc++.h>
using namespace std;
map<int, int> cnt;
int main() {
    int n, l; scanf("%d%d", &n, &l);
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        cnt[x]++;
    }
    int ans = 0, x = n;
    for (ans = 0; ans < n; ans++) {
        x -= cnt[ans];
        if (x + min(cnt[ans], l) <= ans) break;
    } printf("%d\n", ans);
    return 0;
}

78 评论

xiaoliu_lmh 2024-03-05 13:36

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int n, m;//n篇论文，最多可以引用m篇论文
int c[N];

bool check(int mid)
{
    int cnt = 0, backup = m;
    for (int i = 0; i < n; i ++)
    {
        if (c[i] >= mid) cnt ++;
        else if (backup && c[i] + 1 >= mid) cnt ++, backup --;
    }

    return cnt >= mid;
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> c[i];

    int l = 0, r = 1e5;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }

    cout << l << '\n';

    return 0;
}

acwing_93302 2024-03-06 09:37

妙啊，直接check答案

acwing_18509 2024-03-07 20:10

为什么不用排序？？

xiaoliu_lmh 2024-03-07 20:53 回复了 acwing_18509 的评论

统计够不够就可以了，不需要排序

acwing_18509 2024-03-07 21:03 回复了 xiaoliu_lmh 的评论

！懂了懂了

upp1 2024-03-08 20:02 回复了 xiaoliu_lmh 的评论

cnt是什么

Da_233 2024-03-08 23:31 回复了 acwing_18509 的评论

因为相当于做了一次桶排序

xiaoliu_lmh 2024-03-09 00:21 回复了 upp1 的评论

记录个数的，够不够mid个

dflying 2024-03-16 10:55

太妙了

南烟_66 2024-03-24 17:07

bool check(int mid){
int res = 0;
for(int i = 0;i < n;i){
if(a[i] >= mid) res;
else if(m && a[i] + 1 >= mid){
res++;
m–;
}
}
return res >= mid;
}
为什么这里直接用m会有一个测试点过不了

xiaoliu_lmh 2024-03-24 20:09 回复了南烟_66 的评论

会进行多次check，要保证每次进入check的时候m都是相同的。所以要备份一下

南烟_66 2024-03-25 14:59 回复了 xiaoliu_lmh 的评论

懂了哈哈，谢谢

Ustinian_064 2024-04-12 19:28

为什么我感觉有点问题呢，在check的elseif里如果每次需要backup加的是2怎么办呢，比如说 2 4 0 0 是不是每次需要加2，怎么判断啊

whx__xx 2024-10-29 10:11 回复了 Ustinian_064 的评论

题意有限制（她只能引用每篇她的论文至多一次。）

Aiden_927 2023-10-03 23:21

x -= cnt[ans] 之后，x表示：引用量 > ans 的文章的篇数
x + min(cnt[ans], l) 表示：引用量包括ans的或是加上L个引用之后引用量> ans的文章的篇数

烨笙 2024-03-24 19:29

记录一下每个数出现的次数然后前缀和就行了，别的不需要；

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
typedef pair<int,int> PII;
int n,m;int a[N],id,maxn;


int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>id,a[id]++,maxn=max(maxn,id);
    for(int i=1;i<=maxn+5;i++) 
    {
        a[i]+=a[i-1];
        int sum=0;
        sum+=n-a[i-1];
        //cout<<sum<<' ';
        if(i>=2) sum+=min(m,a[i-1]-a[i-2]);
        else sum+=min(m,a[i-1]);
        if(sum<i)
        {
            cout<<i-1;return 0;
        }
    }
    return 0;
}

月下初拥 2024-04-06 10:38

虽然但是，大佬能讲解一下吗，orz

JcWing 2022-07-16 22:12

第二种做法不用开 $map$ 吧，数据范围说了输入的每个数 $\le 10^5$ ，开个数组应该就够了。这样时间复杂度还能省一个 $log$

长途 2022-03-18 14:29

我的ac代码也很玄学

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define debug(x) cout<<"[debug]"#x<<"="<<x<<endl
typedef pair<int,int> pii;
typedef long long ll;
const double eps=1e-8;
const int INF=0x3f3f3f3f;
const int N=100005;
int c[N];
int jishu[N];
int s[N];
int l;
int n;
int main()
{
    scanf("%d%d",&n,&l);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        jishu[c[i]]++;
    }

    for(int i=100000;i>=0;i--)
    {
        s[i]=s[i+1]+jishu[i];
    }

    int res=-1;
    for(int i=100000;i>=0;i--)
    {
        if(s[i+1]<=i+1)
        res=max(res,s[i+1]+max(min(min((i+1)-s[i+1],l),jishu[i]),0));
    }
    printf("%d\n",res);
}

打旋的水 2024-04-07 21:27

浅显的写了一下自己的理解：
https://www.acwing.com/solution/content/238301/

奶白色乳子 2024-04-01 11:57

比y总讲的好理解

juuu- 2024-03-23 17:41

#include[HTML_REMOVED]
using namespace std;
const int N=1e5+10;
int n,m;//

int a[N];
bool check(int mid){
int ans=0;
for(int i=1;i<=mid;i){
if(a[i]>=mid)continue;
else if(a[i]+1>=mid){
ans;
}
}
if(ans>m)return 0;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1,greater[HTML_REMOVED]());
int l=0,r=n;
while(l<r){
int mid=(l+r+1)/2;
if(check(mid))l=mid;
else r=mid-1;
}
cout<<r;
return 0;
}
大佬可以帮我看看码

花生酥hsu 2024-03-21 15:47

强

dflying 2024-03-15 01:14

妙啊，O(n)的做法

hanhyojoo 2024-03-08 19:35

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
using namespace  std;
const int N=1e5+10;
int tr[N],p[N];
int n,k;
int maxv;
int lowbit(int x)
{
      return x&-x;
}
void add(int x,int a)
{
     for(int i=x;i<=N;i=i+lowbit(i))
          tr[i]+=a;
}
int sum(int x)
{          int res=0;
      for(int i=x;i;i=i-lowbit(i))
            res+=tr[i];
            return res;
}
bool check(int x)
{     int res=0;

    res=sum(x-1)-sum(x-2);
      res=min(res,k);
    if(sum(maxv)-sum(x-1)+res>=x)
      return true;
      else
      return false;
}
signed main()
{    ios::sync_with_stdio(false);   
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {    
          cin>>p[i];
          p[i]=p[i]+1;
          maxv=max(p[i],maxv);
          add(p[i],1);
    }
    sort(p,p+n);
    int l=1,r=n+1;
    while(l<r)
    {  int mid=l+r+1>>1;
       if(check(mid))
        l=mid;
        else
        r=mid-1;
    }
    cout<<l-1;
    return 0;
}这样写有啥问题 过了一半11/19样例