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

这是我的第一版，超级简单，但有个点ac不掉，想了半天才发现我理解错那个规律了

struct people{
    int a,b;
    bool operator <(const people x) const{
        return a*b<x.a*x.b;
    }
}p[1005];

int main() {
    int n;
    cin>>n;
    for(int i=0;i<=n;i++) cin>>p[i].a>>p[i].b;
    sort(p+1,p+n+1);
    
    int hp[10010]={1},len=1;//high precision数组
    for(int i=1;i<=n;i++) {//循环n次
        for(int j=0;j<len;j++) hp[j]*=p[i-1].a;
        for(int j=0;j<len;j++)
            if(hp[j]>9) {hp[j+1]+=hp[j]/10;hp[j]%=10;}
        while(hp[len]) {
            hp[len+1]+=hp[len]/10;
            hp[len++]%=10;
        }
    }
    for(int i=len-1;i>=0;i--) {
        hp[i-1]+=hp[i]%p[n].b*10;
        hp[i]/=p[n].b;
    }
    while(!hp[len-1]) {
        if(len==1) break;
        len--;
    }
    
    for(int i=len-1;i>=0;i--) cout<<hp[i];
    return 0;
}
 

其实思路也真的很简单
1.首先找到规律，按照a*b从小到大的顺序排列，证明方法请自行看题解，不过这个排列方式并不是说最后一个大臣获得的coins一定最多（虽然9个测试点都是这样，不要问我是怎么知道的QAQ），只能说明获得coins最多里且最少（有点拗口）一定在这样一个排列方式里。

2.排好序后直接依次算出每个大臣所获的coins，记录下最大的那个输出即可。

注：
1.因为coins可能会很大，所以需要用到高精
2.乘法的高精很简单，但不同于加法，它的最高位可能进的不止一位，所以用while循环直到最高位不再进位为止
3.最讲究细节的就是高精除法了，规则是从高位到底位，除以除数得到的商保留，余数乘以10放进下一位。

反正我是出错了好多次，而且是要从一个数组除以一个数存储到另一个数组，所以最好的方法是借助一个temp
4.单独开一个max高精数组每次与计算出的coins比较，及时更新最大值

struct people{//king and his ministers
    int a,b;
    bool operator <(const people x) const{
        return a*b<x.a*x.b;
    }
}p[1005];
//三个high precision数组
int mul[10010]={1},len1=1;//每个大臣乘法后得到的数
int dev[10010]={1},len2=1;//每个大臣出发后得到的数
int maj[10010]={0},len3=1;//每次计算出第i个大臣所获得的coins后，顺便比较，记录下最大的那一个
//div重名了，用dev替代；max重名了，用maj代替。



void multiply(int num) {
    for(int i=0;i<len1;i++) mul[i]*=num;//每个位上分别乘以低精度的num
    for(int i=0;i<len1;i++)//从低到高依次进位
        if(mul[i]>9) {mul[i+1]+=mul[i]/10;mul[i]%=10;}
    while(mul[len1]) {//拓展最高位
        mul[len1+1]+=mul[len1]/10;
        mul[len1++]%=10;
    }
}

void division(int num) {
    len2=len1;//因为除法是建立在乘法计算后得出的数的基础上
    /*dev[len2-1]=mul[len1-1];
    for(int i=len2-1;i>=0;i--) {
        if(i) dev[i-1]=mul[i-1]+dev[i]%num*10;
        dev[i]=dev[i]/num;
    }*/
    int temp=0;
    for(int i=len2-1;i>=0;i--) {//从高位到低位，除以num得到的商保留，余数乘以10放进下一位
        temp=temp*10+mul[i];
        dev[i]=temp/num;
        temp%=num;
    }
    while(!dev[len2-1]) {//删除前导0
        if(len2==1) break;
        len2--;
    }
    /*int temp=len;
    for(int i=temp-1;i>=0;i--) {
        if(hp[i]||len==1) break;
        len--;
    }*/
}

void maximize(){
    if(len2>len3) {//如果该大臣的coins位数大于记录最大的coins，就更改maj
        for(int i=0;i<len2;i++) maj[i]=dev[i];
        len3=len2;
    }
    else if(len2==len3) {//如果位数相同，从高位到低位，比较每个位上数字大小
        for(int i=len2-1;i>=0;i--)
            if(dev[i]>maj[i]) {//一旦发现某位上数字大就更新maj
                for(int j=0;j<len2;j++) maj[j]=dev[j];
                break;//第一次发现后就可以停止了
            }
    }
}
int main() {
    int n;
    cin>>n;
    for(int i=0;i<=n;i++) cin>>p[i].a>>p[i].b;
    sort(p+1,p+n+1);
    
    for(int i=1;i<=n;i++) {//循环n次
        multiply(p[i-1].a);
        division(p[i].b);
        maximize();
    }

    for(int i=len3-1;i>=0;i--) cout<<maj[i];
    return 0;
}