思路

抽象成 0-1 背包

接纳第 $i$ 天来的动物需要的总果实为

因为它要连续吃 $(n-i+1)$ 天。 若留下这只动物，该权重一次性从仓库扣除即可，不会影响“每天都够吃”的合法性（前缀消耗必然 ≤ 总消耗）。

问题转化为：

有 $n$ 个物品，第 $i$ 个物品重量 $w_i$，价值均为 1，背包容量 $X$。求最多能选多少件物品。

贪心最优性

• 价值都相同，只要尽量选重量小的物品，就能获得最多件数。
• 因此将所有 $w_i$ 按升序排序，依次累加直到容量用完即可。

溢出处理

• $X\le 10^{18}$，若 $c_i > \dfrac{X}{n-i+1}$，则 $w_i>X$ 必不能选，可直接丢弃，避免乘法溢出。
• 其余 $w_i\le X$，用 64 位整数即可安全存储。

算法步骤

1. 读入 $n,X$ 及所有 $c_i$。

2. 对每只动物计算 $k=n-i+1$：

   • 若 $c_i > X/k$，跳过；
   • 否则记录 $w_i=c_i\times k$。

3. 对所有可行 $w_i$ 排序。

4. 顺序遍历，累计重量，若超过 $X$ 则停止。

5. 输出已累计的数量。

复杂度分析

• 统计权重：$O(n)$
• 排序：$O(m\log m)$，$m$ 为可行动物数，$m\le n$
• 总计：时间 $O(n\log n)$，空间 $O(n)$

代码

Python

# 读取输入
import sys
MOD = 998244353  # 题目未要求取模，这里无需使用

n, X = map(int, sys.stdin.readline().split())
c = list(map(int, sys.stdin.readline().split()))

w = []                               # 存放可行权重
for i, v in enumerate(c, 1):         # i 从 1 开始
    k = n - i + 1                    # 需要喂食的天数
    if v > X // k:                   # 重量必超出背包，跳过
        continue
    w.append(v * k)

w.sort()                             # 升序
tot = ans = 0
for val in w:
    if tot + val > X:                # 容量不足，结束
        break
    tot += val
    ans += 1

print(ans)

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long INF = (long) 4e18;      // 足够大的哨兵

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long X = Long.parseLong(st.nextToken());

        st = new StringTokenizer(br.readLine());
        List<Long> list = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            long v = Long.parseLong(st.nextToken());
            long days = n - i + 1L;
            if (v > X / days) continue;       // w_i > X，必不能选
            list.add(v * days);
        }

        Collections.sort(list);               // 升序
        long sum = 0, cnt = 0;
        for (long w : list) {
            if (sum + w > X) break;
            sum += w;
            cnt++;
        }
        System.out.println(cnt);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int64 X;
    if (!(cin >> n >> X)) return 0;

    vector<int64> w;                        // 存放权重
    for (int i = 1; i <= n; ++i) {
        int64 c; cin >> c;
        int64 days = n - i + 1;
        if (c > X / days) continue;         // 无法放入
        w.push_back(c * days);
    }

    sort(w.begin(), w.end());               // 升序
    int64 sum = 0, ans = 0;
    for (int64 v : w) {
        if (sum + v > X) break;
        sum += v;
        ++ans;
    }
    cout << ans << '\n';
    return 0;
}

题目内容

多多先生经营着一个生机勃勃的多多果园。果园里不仅种满了各种果树，还吸引了许许多多可爱的小动物前来定居。

最近，果园的收获季到了，多多先生收获了许多筐香甜的果实。在果园的一角，有一个存放备用果实的大仓库，仓库里有$X$筐果实。

神奇的是，从第$1$天开始，每天早晨都会有一只新的小动物来到果园，希望能在这里定居。每只小动物的食量都不同。如果多多先生允许第$1$天来的小动物留下，那么

这只小动物就会从当天(第$i$天)开始，一直到第$n$天结束，每天都需要吃掉c_i筐果实才能感到幸福。多多先生非常善良，他希望果园里的小动物越多越好。

但是，他也必须保证每一只留在果园的小动物，从它来到的那天起直到第n天，每一天都能吃到足够的食物，绝不能有任何一只小动物挨饿。

多多先生可以选择拒绝任何一只前来定居的小动物。被拒绝的小动物会默默地离开，不会消耗果园的任何果实。

请问，在第$n$天结束时，多多先生的果园里最多能有多少只幸福的小动物?

输入描述

输入的第一行包含两个整数$n$和$X$($1≤n≤200000,1≤X≤10^{18})$，分别表示果园收获季的总天数，以及初始时仓库里备用的果实筐数。

输入的第二行包含$n$个整数$c_1,c2,...,c_n(1≤c_i≤300)$，其中$c_i$表示第$i$天前来定居的小动物的

每日食量。数字之间用空格隔开。

输出描述

输出一个整数，表示在第$n$天结束时，在保证所有小动物每天都能吃饱，一直幸福的前提下，果园里所能拥有的小动物的最大数量。

样例1

输入

3 8
2 2 2

输出

2 

样例2

输入

3 12
2 2 2

输出

3