题解：P15026 [UOI 2021 II Stage] 商店

· · 题解

题目主要意思：给定一批珠宝的价格，要选择一个售价，所有不低于这个售价的珠宝都按该价格卖出，求能获得的最大总收入。

简单说：选一个价格，让该价格乘以不低于它的珠宝数量，结果最大。

思路：先把所有珠宝价格按从高到低排好序。然后逐个看每个价格作为候选售价时，能卖出多少件（就是排在它及它后面的数量，因为这些都不低于它）。用这个价格乘以对应的数量，算出来的就是这个售价下的总收入。最后比一比所有候选售价的总收入，最大的那个就是结果。


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;  // 读取珠宝数量
    vector<long long> a(n);  // 用vector存储每件珠宝的价格
    for (int i = 0; i < n; ++i) {
        cin >> a[i];  // 输入每件珠宝的价格
    }
    sort(a.begin(), a.end());  // 对价格进行升序排序，方便后续计算

    long long max_result = 0;  // 存储最大收入
    for (int i = 0; i < n; ++i) {
        // 当前价格为a[i]，此时有(n - i)件珠宝价格不低于a[i]（因为已排序）
        // 计算当前价格下的总收入：价格 * 数量
        long long current = a[i] * (n - i);
        // 如果当前收入大于之前的最大值，更新最大值
        if (current > max_result) {
            max_result = current;
        }
    }
    cout << max_result << endl;  // 输出最大收入
    return 0;
}
###