文章目录

• 1. 题目描述
• 1.1. Limit
• 1.2. Problem Description
• 1.3. Input
• 1.4. Output
• 1.5. Sample Input
• 1.6. Sample Output
• 1.7. Source
• 2. 解读
• 3. 代码

1. 题目描述

1.1. Limit

Time Limit: 1000 ms

Memory Limit: 524288 kB

1.2. Problem Description

蒜头君在玩一种卡牌游戏，他有 n n n 张卡牌，每张卡牌上写着两个正整数 a i , b i a_i, b_i ai​,bi​， a i a_i ai​ 表示这张卡牌的能量值， b i b_i bi​ 表示这张卡牌的魔法值。

蒜头君要从这 n n n 张卡牌中选出一些形成一个卡组，用这个卡组对敌人造成伤害。一个卡组对敌人的伤害是这个卡组中所有卡牌的能量值之和乘其中魔法值最小的一张卡牌的魔法值。

蒜头君想知道他用一个卡组最多能对敌人产生多少伤害。

1.3. Input

第一行，一个正整数 n n n ( 1 ≤ n ≤ 1 0 5 ) (1 \le n \le 10^5) (1≤n≤105)

接下来 n n n 行，每行两个正整数 a i , b i a_i, b_i ai​,bi​ ( 1 ≤ a i , b i ≤ 1 0 6 ) (1 \le a_i, b_i \le 10^6) (1≤ai​,bi​≤106)

1.4. Output

输出一行，包含一个整数，表示蒜头君用一个卡组对敌人产生的伤害的最大值。

1.5. Sample Input

3
1 2
3 4
5 6

1.6. Sample Output

32

1.7. Source

计蒜客 T3057 卡牌游戏 III

2. 解读

STL基本使用。

使用 map 对数据进行存储和排序，first中存储魔法值 b i b_i bi​，second中存储魔法值 b i b_i bi​ 对应的能量值累加 ∑ a i \sum a_i ∑ai​。

按照魔法值 b i b_i bi​ 从高到低排列进行遍历，依次计算最小魔法值 min ⁡ b \min b minb 取 b i b_i bi​ 时能够产生多少伤害。输出所有情况的最大值。

3. 代码

#include <iostream>
#include <map>
using namespace std;

// 存储
map<long long, long long> mp;

int main()
{
    // test case
    int t;
    scanf("%d", &t);
    // a, b
    long long a, b;
    long long minB, maxB = 0, sumA = 0, ans = 0, markAns;
    // 输入
    for (int i = 0; i < t; i++) {
        scanf("%lld %lld", &a, &b);
        // 记录每个魔法值对应的能量值汇总
        // 分情况存储
        if (mp.find(b) != mp.end()) {
            mp[b] += a;
        } else {
            mp[b] = a;
        }
        // 获取最大的魔法值
        if (b > maxB) {
            maxB = b;
        }
    }
    // 初始值
    minB = maxB;
    // 遍历
    for (auto it = mp.rbegin(); it != mp.rend(); it++) {
        // 累加能量值
        sumA += it->second;
        // 更新最小魔法值
        minB = min(minB, it->first);
        // 获取结果
        markAns = minB * sumA;
        // 计算结果中的最大值
        if (markAns > ans) {
            ans = markAns;
        }
    }

    // 输出
    printf("%lld\n", ans);
}

联系邮箱：curren_wong@163.com

Github：https://github.com/CurrenWong

欢迎转载/Star/Fork，有问题欢迎通过邮箱交流。