25届-8.15联想(改编题) - 前端

💻 ACM金牌团队🏅️ | 多次AK大厂笔试｜大厂实习经历

👏 感谢大家的订阅➕ 和喜欢💗 和手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

alt

1️⃣ 第一题有点坑，注意模数是 $10 ^ 8 + 7$

2️⃣ 第二题是一道常见的类型的动态规划，不难

🥠 01.神奇果园的采摘策略

问题描述

LYA 正在经营一个神奇的果园。这个果园里共有 $n$ 棵神奇的果树，编号从 $1$ 到 $n$ 。其中编号为 $i$ 的果树初始结有 $a_i$ 个果实，且保证 $a_i > 0$ 。每天，LYA 需要选择其中一棵还有果实的树进行采摘，她会将该树上所有果实都采摘下来，使得该树上果实数量归零。

有趣的是，每次采摘完成后，其他所有果树会受到魔法影响，立即使得它们树上的果实数量翻倍。LYA 想要以最优方式采摘，使得最后能收集到的果实数量最多。

采摘过程从第 1 天开始，第 $i$ 棵树上初始有 $a_i$ 个果实。LYA 每天选择一棵非空果树采摘，然后其余果树的果实数翻倍，如此循环直到第 $n$ 天采摘完最后一棵非空果树。

请你帮助 LYA 找到最优的采摘方案，使得她能收集到最多的果实。

输入格式

第一行一个整数 $n$ ，表示果树数量。

第二行 $n$ 个整数 $a_1, a_2, ..., a_n$ ， $a_i$ 表示编号为 $i$ 的果树初始果实数量。

输出格式

输出一个整数表示答案。因为结果可能较大，请输出结果模 $100000007$ 的余数。

tips ⚠️ 模数是 $10 ^ 8 + 7$

样例输入

2
1 2

样例输出

数据范围

对于 $100\%$ 的数据， $1 \leq n \leq 50000$ ， $1 \leq a_i \leq 1000000$ 。

题解

从小到大排序后贪心

我们按照果实数量从小到大的顺序采摘果树，

从果实数量最少的树开始采摘，每次采摘后，剩余树的果实数量翻倍，用一个变量记录当前翻倍了多少。
累加每次采摘的果实数量，注意要对大数进行取模操作。

时间复杂度为 $O(n \log n)$ ，主要来自排序。空间复杂度为 $O(n)$ ，用于存储果树数组。

参考代码

Python

# 读取输入
n = int(input())
trees = list(map(int, input().split()))

# 对果树按果实数量排序
trees.sort()

MOD = 100000007
result = 0
multiplier = 1

# 遍历排序后的果树，计算总果实数
for fruits in trees:
    result = (result + fruits * multiplier) % MOD
    multiplier = (multiplier * 2) % MOD

# 输出结果
print(result)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 读取输入
        int n = sc.nextInt();
        long[] trees = new long[n];
        for (int i = 0; i < n; i++) {
            trees[i] = sc.nextLong();
        }
        
        // 对果树按果实数量排序
        Arrays.sort(trees);
        
        long MOD = 1000000007;
        long result = 0;
        long multiplier = 1;
        
        // 遍历排序后的果树，计算总果实数
        for (long fruits : trees) {
            result = (result + fruits * multiplier % MOD) % MOD;
            multiplier = (multiplier * 2) % MOD;
        }
        
        // 输出结果
        System.out.println(result);
        sc.close();
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 读取输入
    vector<long long> trees(n);
    for (int i = 0; i < n; i++) {
        cin >> trees[i];
    }
    
    // 对果树按果实数量排序
    sort(trees.begin(), trees.end());
    
    const long long MOD = 1000000007;
    long long result = 0;
    long long multiplier = 1;
    
    // 遍历排序后的果树，计算总果实数
    for (long long fruits : trees) {
        result = (result + fruits * multiplier % MOD) % MOD;
        multiplier = (multiplier * 2) % MOD;
    }
    
    // 输出结果
    cout << result << endl;
    
    return 0;
}

🍡 02.LYA的精品购物计划

问题描述

LYA 是一位知名时尚博主，她计划在一家新开的精品店购买一系列商品来制作视频。这家店有 $n$ 件商品，从左到右排列，编号为 $1$ 到 $n$ 。LYA 决定从左往右选购，不能跳过中间的商品再回头购买。每件商品最多只能买一个。

对于第 $i$ 件商品，LYA 给它评定了一个基础吸引力值 $a_i$ 。但是，LYA 发现购买顺序会影响她的购物体验。她认为第 $k$ 个购买的商品会给她带来 $w_k$ 倍的额外体验加成。如果第 $k$ 个购买的是商品 $i$ ，那么这件商品带给 LYA 的总体验值就是 $w_k \times a_i$ 。