P9937 [USACO21OPEN] Acowdemia I B 题解

vectorxyz · 2023-12-17 19:50:15 · 题解

一道特别简单的贪心题。

简化题意

本题就是让我们先求一个最大的 h，在根据 l 把后面能补的补一补，最终再求一个 h。

题目分析

一眼贪心。

先将数组从小到大排序，因为要求最大的 h，再在满足要求的最后一个数后数 l 个，分别加上 1，再重复此操作，输出答案。

具体如下图所示（样例二举例）：

核心代码

n = read, l = read;

for(int i = 1;i <= n;i ++ )
{
    cin >> a[i];
}
sort(a + 1,a + 1 + n, greater<int>());

int h =  get();
h ++ ;

while(l > 0 && h > 0) a[h -- ] ++ , l -- ;

sort(a + 1,a + 1 + n, greater<int>());

return cout << get() ,0;