4.2 鲜花礼物

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

YellowStar 有\(n\)朵花，每朵花都有高度，表示为\(a_1,a_2,\cdots ,a_n\)。\(m\)天之后他要把\(n\)朵花作为礼物送给他心爱的小姐姐，不过这\(m\)天里可以通过浇花来让花长高。

由于每天只能浇一朵花，使得该朵花高度加 1。Yellowstar 希望自己送出去的\(n\)朵花中的最低高度值，尽可能大，请你帮帮他。

数据输入

输入的第一行为 2 个数字\(n,m\ (1\leq n\leq 10^5,1 \leq m \leq 10^9)\)，表示有\(n\)朵花，\(m\)天。第二行包含\(n\)个整数，表示鲜花的高度\(a_1,a_2,\cdots,a_n\ (1\leq a_i\leq 10^9)\)。

数据输出

输出一个整数，表示答案。

输入示例 输出示例
6 2
2 2 2 2 1 1		 2
6 1
2 2 2 2 1 1		 1

数据范围

\(80\%\)的得分点，\(m \leq 100000\)； \(20\%\)的得分点，\(m \leq 10^9\)。

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxn 100005
int hight[maxn];
int num[maxn];

//每次浇最矮的一批花就好
int main(){
    int n, m, i, dh;
    while (~scanf("%d%d", &n, &m)){
        for (i = 0; i < n; ++i)
            scanf("%d", &hight[i]);
        sort(hight, hight + n);
        for (i = 1; i < n; ++i){
            dh = (hight[i] - hight[i - 1]);
            if (dh >= m / i)  break;//这样避免使用长整型
            m -= i*dh;//已经保证i\times dh<m了，所以不会溢出
        }
        printf("%d\n", hight[i - 1] + m / i);
    }
    return 0;
}

设计思路与复杂度分析

补短板就好了，但是实现的时候不要去一次一次的模拟，而是一次性将所有最矮的提升到次矮，否则就超时了。注意数据范围！

复杂度分析：排序\(O(n\times logn)\)，数据处理\(O(n)\)，整体时间复杂度\(O(n\times logn)\)。

0%