2022-05-28：某公司计划推出一批投资项目。 product[i] = price 表示第 i 个理财项目的投资金额 price 。 客户在按需投资时，需

2022-05-28：某公司计划推出一批投资项目。 producti = price 表示第 i 个理财项目的投资金额 price 。

客户在按需投资时，需要遵循以下规则：

客户在首次对项目 producti 投资时，需要投入金额 price,

对已完成首次投资的项目 producti 可继续追加投入，

但追加投入的金额需小于上一次对该项目的投入(追加投入为大于 0 的整数),

为控制市场稳定，每人交易次数不得大于 limit。(首次投资和追加投入均记作 1 次交易),

若对所有理财项目中最多进行 limit 次交易，使得投入金额总和最大，请返回这个最大值的总和。

来自银联编程比赛。

答案2022-05-28：

排序，从右往左割羊毛。

代码用rust编写。代码如下：

代码语言：rust复制

fn main() {
    let mut arr: Vec<isize> = vec![2, 5, 5, 7, 7];
    let limit: isize = 20;
    let ans = max_investment(&mut arr, limit);
    println!("ans = {}", ans);
}

fn max_investment(arr: &mut Vec<isize>, mut limit: isize) -> isize {
    const MOD: isize = 1000000007;
    arr.sort();
    let n = arr.len() as isize;
    let mut ans: isize = 0;
    let mut r = n - 1;
    let mut l = r;
    while limit > 0 && r != -1 {
        while l >= 0 && arr[l as usize] == arr[r as usize] {
            l -= 1;
        }
        let big = arr[r as usize];
        let small = if l == -1 { 0 } else { arr[l as usize] };
        let teams = n - l - 1;
        let all = (big - small) * teams;
        if limit >= all {
            ans  = get(big, small   1, teams);
            ans %= MOD;
            limit -= all;
        } else {
            let a = limit / teams;
            ans  = get(big, big - a   1, teams)   (big - a) * (limit % teams);
            ans %= MOD;
            limit = 0;
        }
        r = l;
    }
    return ans % MOD;
}

fn get(up: isize, down: isize, num: isize) -> isize {
    return num * ((up   down) * (up - down   1) / 2);
}

执行结果如下：

在这里插入图片描述

---

左神java代码

java rust limit

0 人点赞