洛谷P1080 [NOIP2012 提高组] 国王游戏

此题用到的算法有贪心和高精度计算

高精度

高精度真的太折磨人了，我搞了好久好久
（PS：python可跳过这一步，它自带高精度)
一开始我想用long long 但这个数据长度已经超过long long了
那就开始用string

高精度乘法

string mul(string a,int b){
//这里可以类似大整数加法的时候要把数据逆转
//同理乘法的时候也是从后往前算
	reverse(a.begin(),a.end());
	vector<int>c;//c记录逆序的答案
	int t=0;
    for(int i=0;i<a.size()||t;i++){
    //这里"||t"的意思是如果a已经算完了还有进位t也要放入c中
        if(i<a.size())t+=(a[i]-'0')*b;
        c.push_back(t%10);
        t/=10;//进位
    }
    //前导0
    while(c.size()>1&&c.back()==0)c.pop_back(); 
    //将最终结果转换为str
    string str;
    for(int i=c.size()-1;i>=0;i--){
    	str+=c[i]+'0';
	}
	return str;
}

高精度除法

这个是不需要返回余数的情况

string div(string a,int b){
	vector<int>c;//c记录逆序的答案
	int r=0;
	//除法的时候是从前往后算不需要逆转
    for(int i=0;i<a.size();i++){
        r = r * 10 + (a[i]-'0');
        c.push_back(r / b);
        r %= b;
    }
    //先翻转把后面的数字提上来，前面的数字放后面
    //这样如果原来前面有0就可以用pop_back()把现在在末尾的0去掉
    //再前导0
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0)c.pop_back();
    string str;
    //转化成字符串
	for(int i=c.size()-1;i>=0;i--){
    	str+=c[i]+'0';
	}
	return str; 
}

如果要返回余数：

//&r：可以让r在函数中改变的值传到主函数中去
//所以在主函数里要先定义一个int r
string div(string a,int b,int &r){
	vector<int>c;
    for(int i=0;i<a.size();i++){
        r = r * 10 + (a[i]-'0');
        c.push_back(r / b);
        r %= b;//跳出循环时r保留下了余数
    }
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0)c.pop_back();
    string str;
	for(int i=c.size()-1;i>=0;i--){
    	str+=c[i]+'0';
	}
	return str; 
}

将整数转化为string

最后高精度都对了没想到栽在了这个地方哭泣😢
竟然忘记把字符串逆转过来

string toString(int x){//整数转字符串 
	string str;
	while(x>0){
		str+=x%10+'0';
		x/=10;
	} 
	reverse(str.begin(),str.end());//忘记逆转了！！
	return str;
}

字符串的大小比较

自带的max不能比较字符串只能建个函数咯
自带比较字符串大小只能从前往后比较不受到长度的影响所有不能省略这个函数
主要是试过了错了…😥

string maxx(string a,string b){
	if(a.size()!=b.size())return a.size()>b.size()?a:b;//长度不同的时候返回长的那个
	return a>b?a:b;//长度相同时返回大的那个
}

贪心部分的理解

现在来讲讲贪心部分的理解吧
一开始我很天真的以为是让左手越小放在越前面，WA了几次才知道才没那么简单
来打个表理解一下吧

当大臣1在大臣2前面时

这里的max是：max(X1/R1，X1L1X2/R2）

互换位置
当大臣2在大臣1前面时

这里的max是：max(X1/R2，X1L2X2/R1）

可以推出：
X1/R1<X1*L2*X2/R1…(1)
X1*L1*X2/R2>X1/R2…(2)
要让交换前的情况优于交换后的情况，必须满足：
X1/R1>X1*L1*X2/R2…(3)
由(1)、(3)可得
X1*L2*X2/R1>X1*L1*X2/R2
整理可得：
L2/R1>L1/R2
L2*R2>L1*R1
综上所述：当l*r小的放前面，最后的max值才会越小

struct dc{
	int l,r;
	bool operator <( const dc &w)const{
		return l*r<w.l*w.r;
	}
}d[N];

贪心部分代码很简短就是理解这个思路

最终AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1100;
struct dc{
	int l,r;
	bool operator <( const dc &w)const{
		return l*r<w.l*w.r;
	}
}d[N];
string toString(int x){//整数转字符串 
	string str;
	while(x>0){
		str+=x%10+'0';
		x/=10;
	} 
	reverse(str.begin(),str.end());//要记得逆转 
	return str;
}
string mul(string a,int b){
	reverse(a.begin(),a.end());
	vector<int>c;//c记录逆序的答案
	int t=0;
    for(int i=0;i<a.size()||t;i++){
        if(i<a.size())t+=(a[i]-'0')*b;
        c.push_back(t%10);
        t/=10;
    }
    while(c.size()>1&&c.back()==0)c.pop_back(); //前导0 
    string str;
    for(int i=c.size()-1;i>=0;i--){
    	str+=c[i]+'0';
	}
	return str;
}
string div(string a,int b){
	vector<int>c;//c记录逆序的答案
	int r=0;
	//除法的时候是从前往后算不需要逆转
    for(int i=0;i<a.size();i++){
        r = r * 10 + (a[i]-'0');
        c.push_back(r / b);
        r %= b;
    }
    //先翻转把后面的数字提上来，前面的数字放后面
    //这样如果原来前面有0就可以用pop_back()把现在在末尾的0去掉
    //再前导0
    reverse(c.begin(),c.end());
    while(c.size()>1&&c.back()==0)c.pop_back();
    string str;
    //转化成字符串
	for(int i=c.size()-1;i>=0;i--){
    	str+=c[i]+'0';
	}
	return str; 
}
string maxx(string a,string b){
	if(a.size()!=b.size())return a.size()>b.size()?a:b;
	return a>b?a:b;
}
int main(){
	int n;
	cin>>n;
	for(int i=0;i<=n;i++){
		cin>>d[i].l>>d[i].r;
	}
	sort(d+1,d+n+1);
	//进行高精度(利用字符串) 
	string mu=toString(d[0].l);
	string di=div(mu,d[1].r);
	string mx=di;
	for(int i=2;i<=n;i++){
		mu=mul(mu,d[i-1].l);
		di=div(mu,d[i].r);
		mx=maxx(mx,di);
	} 
	cout<<mx<<endl;

	return 0;
} 

^{ps：本文仅自己的理解，不一定完全正确。如果您发现了错误，欢迎提醒!}