鱼C论坛

 找回密码
 立即注册
查看: 3256|回复: 6

国王游戏,有一组看不懂的测试数据

[复制链接]
发表于 2019-11-3 16:02:31 | 显示全部楼层 |阅读模式
20鱼币
本帖最后由 阴阳神万物主 于 2019-11-17 18:29 编辑

题目来源:洛谷 P1080 国王游戏
题目描述

恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数  n,表示大臣的人数。
第二行包含两个整数 a  和 b,之间用一个空格隔开,分别表示国王左手和右手上的整数。
接下来 n 行,每行包含两个整数 a 和 b,之间用一个空格隔开,分别表示每个大臣左手和右手上的整数。

输出格式

一个整数,表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

  输入输出样例
输入 #1
输出#1
3 
1 1 
2 3 
7 4 
4 6 
2


我贴出我的代码先,我的思路在更下面:
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct person{
    string left;
    string right;
};
void del_0(string &a){
    while(a[0]=='0' && a.length()-1){
        a.replace(a.begin(),a.begin()+1,"");
    }
}
int comp(string a,string b){
    del_0(a);
    del_0(a);
    if(a.length() > b.length())return 1;
    else if(a.length() < b.length())return -1;
    else{
        for(int i=0;i<a.length();++i){
            if(a[i] > b[i])return 1;
            else if(a[i] < b[i])return -1;
        }
        return 0;
    }
}
void need_one(string &a,int st,char tag=' '){
    if(tag==' ' && a[st]>'0'){
        a[st] -= 1;
        a[st+1] += 10;
        return;
    }
    else{
        need_one(a,st-1,' ');
        if(tag==' '){
            a[st] -= 1;
            a[st+1] += 10;
        }
        return;
    }
}
string sub(string a,string b){
    int i=a.length()-1,j=b.length()-1;
    while(1){
        if(j==-1){
            break;
        }
        if(a[i]>=b[j]){
            a[i] -= b[j]-'0';
            i--;
            j--; 
        }else{
            need_one(a,i,b[j]);
        }
    }
    del_0(a);
    return a;
}
string floordiv(string a,string b){
    int c=comp(a,b);
    if(c < 0)return "0";
    else if(!c)return "1";
    string res="0",d="";
    for(int i=0;i<a.length();++i){
        d += a[i];
        res += '0';
//        cerr<<res<<' '<<d<<' '<<comp(d,b)<<endl;
        while(comp(d,b)>=0){
            d = sub(d,b);
            res[res.length()-1]++;
        }
    }
    del_0(res);
    return res;
}
string mul(string a,string b){
    int la=a.length(),lb=b.length();
    if(la>lb){
        string temp=b;
        b=a;
        a=temp;
        int emp;
        emp = la;
        la = lb;
        lb = emp;
    }
    string c="0";
    for(int i=0;i<la;++i){
        for(int j=0;j<lb;++j){
            int e,f;
            e = la - i - 1;
            f = lb - j - 1;
            int d,k=c.length() - 1 - (i+j);
            d = c[k]-'0';
            d += (a[e]-'0')*(b[f]-'0');
            c[k] = (char)(d%10)+'0';
            if(c.length() < (la+lb)){
                c = '0'+c;
                c[k] += (d/10);
            }
            else c[k-1] += (d/10);
        }
    }
    del_0(c);
//    cerr<<a<<" * "<<b<<" = "<<c<<endl;
    return c;
}
bool how2sort(person a,person b){
//    if(a.left==b.left)return comp(a.right,b.right)==-1;
//    return comp(a.left,b.left)==-1;
    return (comp(mul(a.left,a.right),mul(b.left,b.right))==-1);
}
int main(){
    freopen("testdata.in","r",stdin);
//    freopen("testdata.err","w",stderr);
    int n;
    cin>>n;
    person *queue=new person[n+1];
    for(int i=0;i<=n;++i){
        cin>>queue[i].left>>queue[i].right;
    }
    sort(queue+1,queue+1+n,how2sort);
    string tot="0",now=queue[0].left;
//    cerr<<queue[0].left<<' '<<queue[0].right<<endl;
    for(int i=1;i<=n;++i){
        string get=floordiv(now,queue[i].right);
//        cerr<<now<<" "<<tot<<' '<<get<<" "<<queue[i].left<<' '<<queue[i].right<<endl;
        if(comp(get,tot)==1){
            tot = get;
        }
        if(i<n)now=mul(queue[i].left,now);
    }
    cout<<tot;
    return 0;
}
思路:
先读入数据,按照各位大臣的左右手乘积从小到大排序,依次计算大臣所应得的金币,找出能够获得最多金币的那位大臣获得的金币数,然后输出

为什么根据左右手的乘积排序:
我是看的这里第一个的排序依据

我出错的第一组数据:
数据.zip (3.52 KB, 下载次数: 7)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-11-8 16:32:49 | 显示全部楼层
这数据有误吧……说好的1000位大臣呢……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-11-8 16:42:41 | 显示全部楼层
永恒的蓝色梦想 发表于 2019-11-8 16:32
这数据有误吧……说好的1000位大臣呢……

所以我就犯迷糊了,就是题目来源的测试点2的数据
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-11-9 15:32:58 | 显示全部楼层
阴阳神万物主 发表于 2019-11-8 16:42
所以我就犯迷糊了,就是题目来源的测试点2的数据

不明白
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-11-17 14:40:58 | 显示全部楼层
自顶一波
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2019-11-17 18:31:16 | 显示全部楼层

我终于清楚之前的那个为啥错了,因为我默认了得钱最多的在队尾,殊不知还能在队首……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-3-17 16:58:22 | 显示全部楼层
阴阳神万物主 发表于 2019-11-17 18:31
我终于清楚之前的那个为啥错了,因为我默认了得钱最多的在队尾,殊不知还能在队首……

这样啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-1-15 20:34

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表