题解：P9937 [USACO21OPEN] Acowdemia I B

· · 题解

虽然是相当简单的题目，但是我打模拟赛的时候，这道题挂了。所以特别来写一下题解梳理一下自己的思路~

题意：

给定 N 个数，可以对 L 个数加 1，求最大的 h ，使这 N 个数中至少有 h 个数大于 h 。

思路：

首先找出对于原数组最大的 h ，然后再对于不满足下一个 h 的数尽可能地 +1，最后再来找一遍就可以了。这个思路可能不是最优的，但一定最好想滴~

要注意的：

在执行完 +1 操作后数组可能就不是有序的了，需要再排一遍。

代码：

#include<bits/stdc++.h>
#define int long long
#define N 100005
using namespace std;

int n,m; // n代表N, m代表L
int a[N]; //给定的数字

bool cmp(int x,int y){ //让sort按从大到小排序
    return x>y;
}

signed main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1,cmp); //先排序一遍

    int maxx=1,fx=1; //maxx代表最大的h的下一个，fx代表第一个要加的数
    while(a[maxx]>=maxx && maxx<=n) maxx++; //查找最大的h
    while(a[fx]>=maxx) fx++; //查找第一个不满足条件的数

    for(int i=fx;i<=min(fx+m-1,n);i++) a[i]++; //尽可能增加
    sort(a+1,a+n+1,cmp); //记得再排一遍~

    maxx=1;
    while(a[maxx]>=maxx && maxx<=n) maxx++; //再次查找

    cout<<maxx-1; //输出最大的h
    return 0;
}

再见~