🐷大肚肚
CF-35D普及+/提高

收养动物

2.0s💾 64MB

📋 题目描述

某类动物可在农场中待 nn 天,每天最多增加一只动物,第 ii 天到来的动物每天要吃的粮食为 cic_i,初始有粮草 XX ,请你推算在动物尽可能多的情况下最多能容纳几只动物?动物可以中途来,但是不能中途走

📥 输入格式

第一行包含两个整数 nnXX1n1001 ≤ n ≤ 1001X1041\le X\le10^{4} ),第二行包含 nn 个整数 c1,c2,...,cnc_1,c_2,...,c_n1ci3001\le c_i \le 300)。

注意需要加文件读写:

C++
Loading...

📤 输出格式

仅有一个整数,表示第 nn 天拥有的最大动物数量。

💡 提示

对于第一个例子的说明:DravDe把农场上的第二和第三只动物留下。第二只动物在第二天会吃掉一吨食物,在第三天也会吃掉一吨食物。第三只动物会在第三天吃掉一吨食物。

📝 样例 1

输入
3 4
1 1 1
输出
2

📝 样例 2

输入
3 6
1 1 1
输出
3

📚 来源

💡 题目讲解

1

理解题意

农场里有一群可爱的小动物,它们会在 nn 天里陆续到来。

每天最多来一只新动物,第 ii 天来的动物每天吃掉 cic_i 粮食。农场一开始有 XX 粮食。

重要规则:动物来了就不会走!如果第 ii 天来了一只动物,它从第 ii 天一直待到第 nn 天,每天都吃 cic_i

所以第 ii 天来的动物,总共要吃:

总消耗=ci×(ni+1)从第 i 天到第 n 天的天数\text{总消耗} = c_i \times \underbrace{(n - i + 1)}_{\text{从第 i 天到第 n 天的天数}}

🎯 我们的目标:在粮食预算 XX 之内,尽量多养几只动物。

n=5 天,每只动物从到达日一直待到第 5 天12345动物1: c₁=3, 消耗=3×5=15动物2: c₂=2, 消耗=2×4=8动物3: c₃=4, 消耗=4×3=12动物4: c₄=1, 消耗=1×2=2动物5: c₅=2, 消耗=2×1=2💡 来得越早,吃得越多!第 1 天来的花费是第 5 天的 7.5 倍
1 / 5