简答题 偏难
#23490

国王游戏 【问题描述】 恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个…

国王游戏

【问题描述】

恰逢 H 国国庆,国王邀请 n 位大臣来玩一个有奖游戏。首先,他让每个大臣在左、右手上面分别写下一个整数,国王自己也在左、右手上各写一个整数。然后,让这 n 位大臣排成一排,国王站在队伍的最前面。排好队后,所有的大臣都会获得国王奖赏的若干金币,每位大臣获得的金币数分别是:排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏,所以他想请你帮他重新安排一下队伍的顺序,使得获得奖赏最多的大臣,所获奖赏尽可能的少。注意,国王的位置始终在队伍的最前面。

【输入】

输入文件为 game.in。

第一行包含一个整数 n,表示大臣的人数。

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

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

【输出】

输出文件名为 game.out。

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

【输入输出样例】

【输入输出样例说明】

按 1、2、3 号大臣这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 1、3、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 2、1、3 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 2、3、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9;

按 3、1、2 这样排列队伍,获得奖赏最多的大臣所获得金币数为 2;

按 3、2、1 这样排列队伍,获得奖赏最多的大臣所获得金币数为 9。

因此,奖赏最多的大臣最少获得 2 个金币,答案输出 2。

【数据范围】

对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8;

对于 40%的数据,有 1≤ n≤20,0 < a、b < 8;

对于 60%的数据,有 1≤ n≤100;

对于 60%的数据,保证答案不超过

对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">#define ll long long</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">int n;</p><p style="text-align: left;">int len = 1;//表示高精度数据的长度</p><p style="text-align: left;">int sum[100001] = {0,1};//高精度数据计算结果 </p><p style="text-align: left;">struct minister{</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll left;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ll right;</p><p style="text-align: left;">} m[1000001];</p><p style="text-align: left;">bool cmp(minister a,minister b){</p><p style="text-align: left;"><span style="white-space:pre"> </span>return a.left * a.right &lt; b.left * b.right;</p><p style="text-align: left;">}</p><p style="text-align: left;">void multiplicative(ll x){//高精度乘法 </p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1;i &lt;= len; i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[i] *= x; //各位数乘x,如1111×20 = (1000+100+10+1)×20 </p><p style="text-align: left;"><span style="white-space:pre"> </span>} </p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1;i &lt;= len; i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[i + 1] += sum[i] / 10;//获得进位,因为相乘结果可能为 10 3 13 4,需转化为 1 0 4 3 4</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[i] %= 10;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>len++;//因为是sum[i+1],所以肯定会计算到sum[len+1],所以需要len++</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(sum[len] / 10){//观察最高位是否有进位,因为可能有经过前面的操作后可能有 100 3的情况  </p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[len + 1] = sum[len] / 10;</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[len] %= 10;</p><p style="text-align: left;"><span style="white-space:pre"> </span>len++; </p><p style="text-align: left;"><span style="white-space:pre"> </span>} </p><p style="text-align: left;">    //经过前面的一波操作后,最后可能会导致sum[len]的位置上有0,若为0则需要消除</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(sum[len] == 0)</p><p style="text-align: left;"><span style="white-space:pre"> </span>len--; </p><p style="text-align: left;">}</p><p style="text-align: left;">void division(){//高精度除法,这里只需要进行一次操作,所以不需要参数 </p><p style="text-align: left;"><span style="white-space:pre"> </span>//思路依旧很简单,如2345/5=(2000+300+40+5)/5,小学生除法 </p><p style="text-align: left;"><span style="white-space:pre"> </span>//-&gt;2 3 4 5 -&gt;0 23(3 + 2%5*10) 4 5 -&gt; 0 4 34(4 + 23%5*10) 5 -&gt; 0 4 6 45(5 + 34%5*10)</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = len; i &gt;= 1; i--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[i - 1] += (sum[i] % m[n].right * 10);</p><p style="text-align: left;"><span style="white-space:pre"> </span>sum[i] /= m[n].right;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>//这波操作必然导致一堆前导0,需消除 </p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!sum[len]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>len--;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>//防止除完了</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(len == 0) cout &lt;&lt; "1" &lt;&lt; endl; </p><p style="text-align: left;">} </p><p style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin &gt;&gt; n;</p><p style="text-align: left;">    cin &gt;&gt; m[0].left &gt;&gt; m[0].right;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1;i &lt;= n; i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin &gt;&gt; m[i].left &gt;&gt; m[i].right;</p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(m + 1, m + 1 + n, cmp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 0;i &lt; n; i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>multiplicative(m[i].left); </p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>division();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = len; i &gt;= 1; i--)</p><p style="text-align: left;"><span style="white-space:pre"> </span>cout &lt;&lt; sum[i];</p><p><span style="white-space:pre"> </span></p><p style="text-align: left;">}</p>
这道题暂未补解析。