本帖最后由 阴阳神万物主 于 2019-11-17 18:29 编辑
题目来源：洛谷 P1080 国王游戏
题目描述
恰逢 H 国国庆，国王邀请 n 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入格式
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a 和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
输入输出样例
我贴出我的代码先，我的思路在更下面：#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)
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2019-11-3 16:02:31
置顶卡
千斤顶
显身卡
发表于 2019-11-8 16:32:49
楼主