题解 | [P1080] 国王游戏(简化版)

#include <stdio.h>
#include <stdlib.h>
// 定义大臣结构体
typedef struct 
{
    int a;
    int b;
    long long prod; // 用于排序的乘积 a * b
} Minister;
// 比较函数：按 a * b 升序排列
int compare(const void* p1, const void* p2) 
{
    Minister* m1 = (Minister*)p1;
    Minister* m2 = (Minister*)p2;
    if (m1->prod < m2->prod) return -1;
    if (m1->prod > m2->prod) return 1;
    return 0;
}
int main() 
{
    int n;
    int a0, b0;
    // 输入人数和国王的数字
    scanf("%d", &n);
    scanf("%d %d", &a0, &b0);
    Minister m[61];
    for (int i = 0; i < n; i++) 
    {
        scanf("%d %d", &m[i].a, &m[i].b);
        m[i].prod = (long long)m[i].a * m[i].b;
    }
    // 执行贪心排序
    qsort(m, n, sizeof(Minister), compare);
    long long current_left_prod =a0; // 处理中间乘积
    long long max_gold = 0;
    for (int i = 0; i < n; i++) 
    {
        // 计算当前大臣获得的金币数
        long long current_gold = (long long)(current_left_prod / m[i].b);
        // 更新最大值
        if (current_gold > max_gold) 
        {
            max_gold = current_gold;
        }
        // 累乘左手数字，为下一位大臣做准备
        current_left_prod *= m[i].a;
    }
    printf("%lld\n", max_gold);
    return 0;
}

主要是贪心算法的使用以及合理的看懂公式：

公式所表达的意思是对于第i个大臣的金币数等于前面所有人的左手数乘积除以他自己的右手数。那么如何才能达到最优解呢？这时候可以想到利用左手右手乘积进行升序排序排列，在进行循环即可求出最小。