国王游戏，有一组看不懂的测试数据
本帖最后由 阴阳神万物主 于 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' && 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 > b)return 1;
else if(a < b)return -1;
}
return 0;
}
}
void need_one(string &a,int st,char tag=' '){
if(tag==' ' && a>'0'){
a -= 1;
a += 10;
return;
}
else{
need_one(a,st-1,' ');
if(tag==' '){
a -= 1;
a += 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>=b){
a -= b-'0';
i--;
j--;
}else{
need_one(a,i,b);
}
}
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;
res += '0';
// cerr<<res<<' '<<d<<' '<<comp(d,b)<<endl;
while(comp(d,b)>=0){
d = sub(d,b);
res++;
}
}
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-'0';
d += (a-'0')*(b-'0');
c = (char)(d%10)+'0';
if(c.length() < (la+lb)){
c = '0'+c;
c += (d/10);
}
else c += (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;
for(int i=0;i<=n;++i){
cin>>queue.left>>queue.right;
}
sort(queue+1,queue+1+n,how2sort);
string tot="0",now=queue.left;
// cerr<<queue.left<<' '<<queue.right<<endl;
for(int i=1;i<=n;++i){
string get=floordiv(now,queue.right);
// cerr<<now<<" "<<tot<<' '<<get<<" "<<queue.left<<' '<<queue.right<<endl;
if(comp(get,tot)==1){
tot = get;
}
if(i<n)now=mul(queue.left,now);
}
cout<<tot;
return 0;
}思路：
先读入数据，按照各位大臣的左右手乘积从小到大排序，依次计算大臣所应得的金币，找出能够获得最多金币的那位大臣获得的金币数，然后输出
为什么根据左右手的乘积排序：
我是看的这里第一个的排序依据
我出错的第一组数据：
这数据有误吧……说好的1000位大臣呢…… 永恒的蓝色梦想 发表于 2019-11-8 16:32
这数据有误吧……说好的1000位大臣呢……
所以我就犯迷糊了，就是题目来源的测试点2的数据 阴阳神万物主 发表于 2019-11-8 16:42
所以我就犯迷糊了，就是题目来源的测试点2的数据
不明白 自顶一波 永恒的蓝色梦想 发表于 2019-11-9 15:32
不明白
我终于清楚之前的那个为啥错了，因为我默认了得钱最多的在队尾，殊不知还能在队首…… 阴阳神万物主 发表于 2019-11-17 18:31
我终于清楚之前的那个为啥错了，因为我默认了得钱最多的在队尾，殊不知还能在队首……
这样啊
页:
[1]