国王游戏50分求助

常规
1

代码


#include<bits/stdc++.h>

using namespace std;

int N;

struct n{//大臣和国王结构体
    int l,r;
    bool operator < (n b){
        return l*r<b.r*b.l;
    }
};

vector<n> ns;//大臣和国王

int main(){
    cin>>N;//输入
    N++;
    for(int i=0;i<N;i++){
        int l1,r1;
        cin>>l1>>r1;
        n tmp;
        tmp.l=l1;
        tmp.r=r1;

        ns.push_back(tmp);
    }

    sort(ns.begin(),ns.end());//按照 ar*al<br*bl排序
    int sum=ns[0].l;//前几人的积
    int ans=INT_MIN;//答案
    int flag=1;
    //cout<<ns[0].l<<' '<<ns[0].r<<endl;
    for(auto i:ns){
        if(flag){//国王不计入答案
            flag=0;continue;
        }
        sum*=i.l;
        //cout<<i.l<<' '<<i.r<<' '<<sum/i.r<<endl;
        ans=max(ans,sum/i.r);

    }  cout<<ans<<endl;//输出


    return 0;
}

样例能过，但是这个点不能

输入：
10
5 7
4 2
7 3
7 2
4 4
1 7
5 3
6 1
4 5
2 3
3 7

输出：
134400

我的输出：
403200

代码里保留了一部分调试，这样才能让你知道这是错误代码（手动狗头）

2 个赞
2

没用高精度

2 个赞
3 
#include<bits/stdc++.h>

using namespace std;

int N;

struct n{//大臣和国王结构体
    int l,r;
    bool operator < (n b){
        return l*r<b.r*b.l;
    }
};

vector<n> ns;//大臣和国王

int main(){
    cin>>N;//输入
    N++;
    for(int i=0;i<N;i++){
        int l1,r1;
        cin>>l1>>r1;
        n tmp;
        tmp.l=l1;
        tmp.r=r1;

        ns.push_back(tmp);
    }

    sort(ns.begin(),ns.end());//按照 ar*al<br*bl排序
    int sum=1;//前几人的积
    int ans=INT_MIN;//答案
    int flag=1;
    //cout<<ns[0].l<<' '<<ns[0].r<<endl;
    for(auto i:ns){
        if(flag){//国王不计入答案
            flag=0;continue;
        }

        //cout<<i.l<<' '<<i.r<<' '<<sum/i.r<<endl;
        ans=max(ans,sum/i.r);sum*=i.l;

    }  cout<<ans<<endl;//输出


    return 0;
}
30分
2 个赞
4 
#include<bits/stdc++.h>
struct Node{
   int a,b;
};
void mul(int *a,int b,int *c){
    int len=a[0];
    int i;
    for(i=0;i<len+20;i++)c[i]=0;
    for(i=1; i<=len; i++){
        c[i]+=(a[i]*b);
        c[i+1]+=(c[i]/10);
        c[i]%=10;
    }
    while(c[len+1]>0){
        len++;
        c[len+1]+=(c[len]/10);
        c[len]%=10;
    }
    c[0]=len;
}
void div(int *a,int b,int *c){
    int len=a[0];
    int r=0;
    int i;
    for (i=len; i>=1; i--){
        r=r*10+a[i];
        c[i]=r/b;
        r=r%b;
    }
    while (!c[len]) len--;
    if (!len) len=1;
    c[0]=len;
}
void getMax(int *x,int *y){
    if (y[0]<x[0]) return;
    int i;
    if (x[0]==y[0]){
        for (i=y[0]; i>=1; i--)
            if (y[i]<x[i]) return;
            else if (y[i]>x[i]) break;
	}
    for(i=0;i<=y[0];i++)x[i]=y[i];
}
int main(){
    int n;
    scanf("%d",&n);
    struct Node m[1005];
    int i,j;
    for (i=0; i<=n; i++)
        scanf("%d%d",&m[i].a,&m[i].b);
    for (i=1;i<n;i++)
        for (j=1;j<=n-i;j++)
          	if (m[j].a*m[j].b>m[j+1].a*m[j+1].b){
            	struct Node tmp;
            	tmp=m[j]; m[j]=m[j+1]; m[j+1]=tmp;
          	}
    int p[4100];  // 保存累乘积
    int t[4100];  // 中间结果
    int ans[4100]; // 最终答案
    ans[0]=1;
    ans[1]=0;
    p[0]=1;
    p[1]=1;
	for (i=1;i<=n;i++){
        mul(p,m[i-1].a,t);
        for(j=0; j<=t[0]; j++)p[j]=t[j];
        div(p,m[i].b,t);
        getMax(ans,t);
    }
    for(i=ans[0]; i>=1; i--)printf("%d",ans[i]);
    return 0;
}

AC

2 个赞