鱼C论坛

 找回密码
 立即注册

扫一扫,访问微社区

查看: 231|回复: 3

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

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

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

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

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

  输入输出样例
输入 #1
输出#1
  1. 3
  2. 1 1
  3. 2 3
  4. 7 4
  5. 4 6
复制代码

  1. 2
复制代码



我贴出我的代码先,我的思路在更下面:
  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. using namespace std;
  5. struct person{
  6.     string left;
  7.     string right;
  8. };
  9. void del_0(string &a){
  10.     while(a[0]=='0' && a.length()-1){
  11.         a.replace(a.begin(),a.begin()+1,"");
  12.     }
  13. }
  14. int comp(string a,string b){
  15.     del_0(a);
  16.     del_0(a);
  17.     if(a.length() > b.length())return 1;
  18.     else if(a.length() < b.length())return -1;
  19.     else{
  20.         for(int i=0;i<a.length();++i){
  21.             if(a[i] > b[i])return 1;
  22.             else if(a[i] < b[i])return -1;
  23.         }
  24.         return 0;
  25.     }
  26. }
  27. void need_one(string &a,int st,char tag=' '){
  28.     if(tag==' ' && a[st]>'0'){
  29.         a[st] -= 1;
  30.         a[st+1] += 10;
  31.         return;
  32.     }
  33.     else{
  34.         need_one(a,st-1,' ');
  35.         if(tag==' '){
  36.             a[st] -= 1;
  37.             a[st+1] += 10;
  38.         }
  39.         return;
  40.     }
  41. }
  42. string sub(string a,string b){
  43.     int i=a.length()-1,j=b.length()-1;
  44.     while(1){
  45.         if(j==-1){
  46.             break;
  47.         }
  48.         if(a[i]>=b[j]){
  49.             a[i] -= b[j]-'0';
  50.             i--;
  51.             j--;
  52.         }else{
  53.             need_one(a,i,b[j]);
  54.         }
  55.     }
  56.     del_0(a);
  57.     return a;
  58. }
  59. string floordiv(string a,string b){
  60.     int c=comp(a,b);
  61.     if(c < 0)return "0";
  62.     else if(!c)return "1";
  63.     string res="0",d="";
  64.     for(int i=0;i<a.length();++i){
  65.         d += a[i];
  66.         res += '0';
  67. //        cerr<<res<<' '<<d<<' '<<comp(d,b)<<endl;
  68.         while(comp(d,b)>=0){
  69.             d = sub(d,b);
  70.             res[res.length()-1]++;
  71.         }
  72.     }
  73.     del_0(res);
  74.     return res;
  75. }
  76. string mul(string a,string b){
  77.     if(a.length()>b.length()){
  78.         string temp=b;
  79.         b=a;
  80.         a=temp;
  81.     }
  82.     string c="0";
  83.     for(int i=a.length()-1;i>-1;--i){
  84.         for(int j=b.length()-1;j>-1;--j){
  85.             int d,k=c.length()-(b.length()-j);
  86.             d = c[k]-'0';
  87.             d += (a[i]-'0')*(b[j]-'0');
  88.             c[k]=(char)(d%10)+'0';
  89.             if(c.length() < (1+b.length()-j))c = '0'+c;
  90.             c[k]=(char)(d/10)+'0';
  91.         }
  92.     }
  93.     del_0(c);
  94.     return c;
  95. }
  96. bool how2sort(person a,person b){
  97. //    if(a.left==b.left)return comp(a.right,b.right)==-1;
  98. //    cerr<<a.left<<' '<<a.right<<' '<<b.left<<' '<<
  99. //    b.right<<' '<<mul(a.left,a.right)<<' '<<mul(b.left,b.right)<<
  100. //    ' '<<comp(mul(a.left,a.right),mul(b.left,b.right))<<endl;
  101. //    return comp(mul(a.left,a.right),mul(b.left,b.right))==-1;
  102.     if(a.right==b.right)return (comp(a.left,b.left)==-1);
  103.     return (comp(a.right,b.right)==-1);
  104. }
  105. int main(){
  106.     freopen("testdata.in","r",stdin);
  107.     freopen("testdata.err","w",stderr);
  108.     int n;
  109.     cin>>n;
  110.     person *queue=new person[n+1];
  111.     for(int i=0;i<=n;++i){
  112.         cin>>queue[i].left>>queue[i].right;
  113. //        cerr<<queue[i].left<<' '<<queue[i].right<<endl;
  114.     }
  115.     sort(queue+1,queue+1+n,how2sort);
  116.     string tot=queue[0].left;
  117.     cerr<<tot<<' '<<queue[0].left<<' '<<queue[0].right<<endl;
  118.     for(int i=1;i<=n;++i){
  119.         cerr<<tot<<' '<<queue[i].left<<' '<<queue[i].right<<endl;
  120.         tot = mul(queue[i].left,tot);
  121.     }
  122.     cout<<floordiv(tot,queue[n].right);
  123.     return 0;
  124. }
复制代码
思路:
先读入数据,按照左右手的数据从小到大排序,依次左手相乘,到队末时不再相乘,将之前得到的乘积除以队末的右手,并且向下取整,得到结果。

为什么根据左右手的数据排序:
输入数据全是正整数。
不管前面的乘积是什么,总是最后的人得到的乘积最大,故而只要使队伍最后的人右手数据最大,前面的人左手尽量小即可。
看不懂的那组数据:
数据.zip (181.06 KB, 下载次数: 5)

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
22 
发表于 2019-11-8 16:32:49 | 显示全部楼层
这数据有误吧……说好的1000位大臣呢……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
19 
 楼主| 发表于 2019-11-8 16:42:41 | 显示全部楼层
永恒的蓝色梦想 发表于 2019-11-8 16:32
这数据有误吧……说好的1000位大臣呢……

所以我就犯迷糊了,就是题目来源的测试点2的数据
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
最佳答案
22 
发表于 7 天前 | 显示全部楼层
阴阳神万物主 发表于 2019-11-8 16:42
所以我就犯迷糊了,就是题目来源的测试点2的数据

不明白
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号

GMT+8, 2019-11-16 01:39

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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