题目梗概

有n个大臣，他们可以拿到他们之前所有人左手数的乘积除以他的右手，问是否能通过调换位置来使拿钱最多的大臣拿的钱最少。

 

思考

贪心证明:

设相邻的两个人$i, i + 1$。设$A[i] \times B[i] \leqslant  A[i + 1] B[i + 1]$，i之前所有人的左手乘积为S。

则，$ans1 = max \left (\frac{S}{B[i]} , \frac{S}{A[i] \times B[i+1]}  \right )$

若交换

$ans2 = max \left (\frac{S}{B[i+1]} , \frac{S \times A[i+1]}{B[i]} \right )$

$\because A[i] \times B[i] \leqslant  A[i + 1] B[i + 1]$

$\therefore \frac{S \times A[i]}{B[i+1]} \leqslant  \frac{S \times A[i + 1]}{B[i]}$

$\because \frac{S}{B[i+1]} \leqslant\frac{ S \times A[i] }{ B[i + 1]}$

$\therefore ans2 =\frac{ S \times A[i + 1]}{B[i]} $

$\therefore ans1<=ans2$

 

代码实现比较烦了，高精度乘，高精度除。折腾了两小时还是没写出来。找了一篇题解，发现自己太傻比。

#include
     
      #include
      
       #include
       
        #define STR string   // 搞个笑 方个便 #define LEN length()#define B begin()#define E end()#define tonum(X) for (o=0;o
        
         >n;w.s="1";ans.s="0";   //w.s是存前面所有左手的成绩，ans.s就是答案 （最大值）     for (i=0;i<=n;i++)        cin>>m[i].x>>m[i].y,m[i].s=times(m[i].x,m[i].y);   //读入+左右相乘     sort(m+1,m+n+1,cmp);  //将每位大臣的左手右手乘积排序   之后在算答案便是正确答案 证明该题的最底下的题解     for (i=0;i<=n;i++)   //计算     {        an.s=divide(w.s,m[i].y);   //将an.s变成前面所有人左手的乘积除以这个人右手的乘积         if (!cmp(an,ans))ans.s=an.s;   //比较一下，如果an.s更大的话那么an.s就是目前的最大值 把ans.s变成an.s  到最后的最大值就是ans.s        w.s=times(w.s,m[i].x);   //更新前面所有人的乘积     }    cout<