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

Sweet_Corn · 2026-01-25 16:22:49 · 题解

题面翻译

给你一个正整数 n 和一个长度为 n 的序列 a，你需要进行以下操作：

• 选择一个正整数 k。
• 以 k \times m 枚硬币的总价，购买所有 m 件价格不低于 k 的珠宝。换句话说，每件满足 a_i \ge k 的珠宝，他将以单价 k 购买。

现在，你需要求出最大金额是多少。

思路

先排序，然后枚举每个价格作为最低价格 k，计算满足条件的珠宝数量 m，从而得到收益 k \times m，并记录最大值。

注意：不开 long long 见祖宗。

时间复杂度 O(n \log n)。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, a[100005], ans;
signed main(){
    cin >> n;
    for(int i = 1; i <= n; i++)cin >> a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; i++){
        int k = a[i], m = n - i + 1;
        ans = max(ans, k * m);
    }
    cout << ans;
    return 0;
}

制作不易，可以留下一个关注喵！愿审核通过！