题解：P9937 [USACO21OPEN] Acowdemia I B

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

题意：

给定

N

个数，可以对

L

个数加

1

，求最大的 $h$ ，使这 $N$ 个数中至少有

h

个数大于

h

。

思路：

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

要注意的：

在执行完

+1

操作后数组可能就不是有序的了，需要再排一遍。

代码：

CPP

#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;
}

再见~

题解：P9937 [USACO21OPEN] Acowdemia I B

文章操作

题意：

思路：

要注意的：

代码：

相关推荐

评论

题解：P9937 [USACO21OPEN] Acowdemia I B