首页 > 代码库 > [贪心][高精度][NOIP]国王游戏
[贪心][高精度][NOIP]国王游戏
题目梗概
有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<string>#include<iostream>#include<algorithm>#define STR string // 搞个笑 方个便 #define LEN length()#define B begin()#define E end()#define tonum(X) for (o=0;o<X.length();o++)X[o]-=48 //字符串转数字 using namespace std;int o,u,i,n;struct man{STR x,y,s;}m[1001],w,ans,an; //x左手,y右手,s是两手乘积 STR divide(STR a,STR b) //高精除以低精，因为题目说右手最多才10000，所以高/低就行了 { STR c;int d=0,k=1,p=0;tonum(a); for (o=b.length()-1;o+1;o--)p+=(b[o]-48)*k,k*=10; for (o=0;o<a.LEN;o++) c.push_back((d*10+a[o])/p+48),d=(d*10+a[o])%p; while (c[0]==48)c.erase(c.B,c.B+1); return c;}STR times(STR a,STR b) //高精乘 { STR c;c.resize(a.LEN+b.LEN,0); reverse(a.B,a.E);reverse(b.B,b.E); tonum(a);tonum(b); for (o=0;o<a.LEN;o++) for (u=0;u<b.LEN;u++) c[o+u]+=a[o]*b[u],c[o+u+1]+=c[o+u]/10,c[o+u]%=10; reverse(c.B,c.E); while (!c[0])c.erase(c.B,c.B+1); for (o=0;o<c.length();o++)c[o]+=48; return c;}bool cmp(man a,man b) //比较函数 { if (a.s.LEN<b.s.LEN)return 1; if (b.s.LEN<a.s.LEN)return 0; return a.s<b.s;}int main(){ cin>>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<<ans.s; //华丽di输出 return 0; //华丽di结束 }
[贪心][高精度][NOIP]国王游戏
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。