【题目来源】
洛谷：P1080 [NOIP 2012 提高组] 国王游戏 - 洛谷
【题目描述】
恰逢 H 国国庆，国王邀请 \(n\) 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 \(n\) 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
【输入】
第一行包含一个整数 \(n\)，表示大臣的人数。
第二行包含两个整数 \(a\) 和 \(b\)，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 \(n\) 行，每行包含两个整数 \(a\) 和 \(b\)，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
【输出】
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
【输入样例】
3
1 1
2 3
7 4
4 6
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P1080 国王游戏》 #贪心# #高精度# #排序# #NOIP提高组# #2012#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 全局变量：
// n: 除国王外的大臣数量
// slen: 当前乘积的位数
// s[1000000]: 存储乘积结果（逆序存储）
// ans[1000000]: 存储除法结果
int n, slen = 1, s[1000000] = {1}, ans[1000000];// 大臣结构体：a-左手数字，b-右手数字
struct people
{int a, b;
} p[1005];/*** 比较函数，用于排序大臣* @param p1 第一个大臣* @param p2 第二个大臣* @return 是否p1的a*b小于p2的a*b*/
bool cmp(people p1, people p2)
{return p1.a * p1.b < p2.a * p2.b;
}/*** 大数乘法* @param n 乘数*/
void mul(int n)
{int tmp = 0;// 先计算每一位的乘积for (int i = 0; i < slen; i++){s[i] *= n;}// 处理进位for (int i = 0; i < slen; i++){tmp = tmp + s[i];s[i] = tmp % 10;tmp = tmp / 10;}// 处理最高位的进位while (tmp != 0){s[slen] = tmp % 10;slen++;tmp = tmp / 10;}return;
}/*** 大数除法* @param n 除数*/
void div(int n)
{int tmp = 0;// 从高位到低位进行除法for (int i = slen - 1; i >= 0; i--){tmp = tmp * 10 + s[i];ans[i] = tmp / n;tmp = tmp % n;}return;
}/*** 打印结果*/
void print()
{int tmp = slen;// 处理特殊情况if (slen == 1){if (s[slen - 1] == 1){cout << 0;return;}}// 跳过前导零while (ans[tmp] == 0){tmp--;if (tmp == -1){cout << 1;return;}}// 输出结果（逆序输出）for (int i = tmp; i >= 0; i--){cout << ans[i];}return;
}int main()
{// 输入数据cin >> n;for (int i = 0; i <= n; i++){cin >> p[i].a >> p[i].b;}// 按a*b排序大臣（从第二个开始）sort(p + 1, p + n + 1, cmp);// 计算所有大臣左手的乘积for (int i = 0; i < n; i++){mul(p[i].a);}// 除以最后一个大臣的右手数字div(p[n].b);// 输出结果print();return 0;
}
【运行结果】
3
1 1
2 3
7 4
4 6
2