国王的游戏（贪心推公式）

上述为引用洛谷题解

说明：高精度计算的板子应提前书写，贪心策略很重要

#include<algorithm>//用到sort
#include<cstring>//用到memset
using namespace std;
const int MAXN = 1010, MAXM = 10010;//注意高精数组开到10000
struct Node{//一个人
	int l, r;
}a[MAXN];
int pro[MAXM], ans[MAXM], tmp[MAXM];//左手乘积，答案，临时数组
int read(){//快读
	int x = 0,f = 1;//记录数和符号
	char c = getchar();//读入字符
	while(c < '0' || c > '9'){//只要不是数
		if(c == '-') f = -1;//是负号就记录
		c = getchar();
	}
	while(c >= '0' && c <= '9'){//只要是数
		x = x * 10 + c - '0';//挪位再加
		c = getchar();
	}
	return x * f;//返回数乘符号
}
bool cmp(Node aa,Node bb){//排序的比较函数
	return aa.l * aa.r < bb.l * bb.r;//按左右手数的乘积从小到大
}
void copy(int *aa,int *bb){//复制
	for(int i = 0; i < MAXM; i++) aa[i] = bb[i];
}
bool more(int *aa,int *bb){//比较
	for(int i = MAXM - 1; i >= 0;i--){
		if(aa[i] > bb[i]) return 1;
		if(aa[i] < bb[i]) return 0;
	}
	return 0;//注意这里也要写上，写0写1随便
}
void times(int *aa,int num){//乘法
	for(int i = MAXM - 2; i >= 0; i--) aa[i]*=num;//先乘
	for(int i = 0; i < MAXM - 1; i++){//再进位
		aa[i + 1] += (aa[i] / 10);//先加前一位
		aa[i] %= 10;//在处理这一位
	}
}
void div(int *aa,int *bb,int num){//除法
	memset(bb,0,sizeof(bb));//赋为0
	int x=0;
	for(int i = MAXM - 1; i >= 0; i--){//从高位到低位
    	x = x * 10 + aa[i];//挪位再加
		bb[i] = x / num;//记录
		x %= num;//模上
	}
}
void print(int *aa){//输出
	bool flag = 0;//记录是否能输出
	for(int i = MAXM - 1; i >= 0; i--){
		if(!flag){//如果不能
			if(aa[i]) flag = 1;//找到第一个不是0的位，可以输出了
			else continue;//还是不能
		}
		printf("%d",aa[i]);//输出，不用空格或换行
	}
}
int main(){//主函数
	int n = read();
	for(int i = 0; i <= n; i++) a[i].l = read(), a[i].r = read();
	sort(a + 1, a + n + 1, cmp);//排序
	pro[0] = 1;//注意乘积数组初始值为1
	for(int i = 0; i <= n; i++){//注意从0开始，国王
		div(pro, tmp,a[i].r);//先除到tmp上
		if(more(tmp, ans)) copy(ans, tmp);//比较，满足就复制
		times(pro, a[i].l);//自乘
	}
	print(ans);//输出
	return 0;//华丽结束
}