思路：贪心

分别计算每种花所需要的水量，第$i$种花需要的水量为$w[i]\times (n-i)$

然后对花按照所需要的水量从小到大进行排序，优先浇需要水量少的花

时间复杂度

$O(nlogn)$

代码

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    int a[n];
    vector<int> b(n, 0);
    for(int i = 0; i < n; ++i){
        cin>>a[i];
        b[i] = (n - i) * a[i];
    }
    sort(b.begin(), b.end());
    int res = 0, cnt = 0;
    for(int i = 0; i < n; ++i){
        cnt += b[i];
        if(cnt > m) break;
        res++;
    }
    cout<<res;
}

python代码

n, m = list(map(int, input().split()))
nums = list(map(int, input().split()))

def solve(n, m, nums):
    res = 0
    water = [0] * n
    for i, x in enumerate(nums):
        water[i] = x * (n - i)
    water.sort()
    tmp = -1
    for i, x in enumerate(water):
        tmp += x
        if tmp > m:
            res = i
            break

    return res if tmp != -1 else 0


print(solve(n, m,nums))

Java代码

import java.util.*;

public class Main{

    public static void main(String[]args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        int[]arr=new int[n];
        for(int i=0;i<n;i++){
            arr[i]=in.nextInt()*(n-i);
        }
        Arrays.sort(arr);
        int cnt=0; 

        for(int i=0;i<n;i++){
            if(m-arr[i]>=0){
                cnt++;
                m-=arr[i];
            }
        }
        System.out.println(cnt);

    }

}

题目描述

小红在闲暇时间喜欢养花。某次小红去一个城市出差 $n$ 天，他带了一些花的种子，如果他种下了，那么那种花就会在特定的时间开放。

现在已知第i种花会在第i天开放，并且开放之后每天都要用 $a_i$ 的水。

举个例子，当 $n=3,a=[1,2,3]$ 时，如果小红种下了第二种花的种子，那么他就要在第二天、第三天和第四天各浇灌 $2$ 升水，总共是 $6$ 升水。

但是由于小红出差经费有限，小红可以用到养花上的水量为 $m$ 升。现在小红想知道，如果他可以放弃一部分种子，最多能种多少种花呢？

输入描述

输入第一行两个正整数 $n$ 和 $m$ 。（$1 \leq n \leq 100，1 \leq m \leq 10^6$）

输入第二行是 $n$ 个正整数 $a_i$ （$1 \leq ai \leq 10^4$）表示每种花开放后每天的耗水量。

输出描述

输出一个整数 $ans$ 表示小红最多可种的花的种数。

样例。

样例输入

5 20
4 6 2 3 5

输出

3

说明

小红可以种下第三种第四种第五种花，之后第三天用水$2$升，第四天用水$5$升，第五天用水$10$升，总用水量 $2+5+10=17$ 升。

样例2

输入

5 100
5 4 3 2 1

输出

5