锐客网

  1. 首页 > it技术 > >

贪心|P1080 国王游戏(贪心+高精度乘除及大数比较)

https://www.luogu.org/problemnew/show/P1080
题目描述
恰逢 H 国国庆，国王邀请 n位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 n 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输入输出格式
输入格式：
第一行包含一个整数 n，表示大臣的人数。
第二行包含两个整数 a和 b，之间用一个空格隔开，分别表示国王左手和右手上的整数。
接下来 n 行，每行包含两个整数 a 和 b，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。
输出格式：
一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
输入输出样例
输入样例#1：

3 1 1 2 3 7 4 4 6

输出样例#1：
2

说明
【输入输出样例说明】
按 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。
【数据范围】
【贪心|P1080 国王游戏(贪心+高精度乘除及大数比较)】对于 20%的数据，有 1≤ n≤ 10,0 < a,b < 8；
对于 40%的数据，有 1≤ n≤20,0 < a,b < 8；
对于 60%的数据，有 1≤ n≤100；
对于 60%的数据，保证答案不超过 10^9 ；
对于 100%的数据，有 1≤n≤1,000,0 NOIP 2012 提高组 第一天 第二题
Ac_code:
/*
举个栗子：
3 1 1 2 100 3 50 4 1

栗子加…推理得出乘积小的应该排在前面，再加上乘积值最大将近10^4000
所以还要高精度计算`！
*/
#include #include #include using namespace std; char aim[4500],temp[4500]; char c1[4500],c2[4500],ans[4500]; struct person { int r; int l; bool operator<(const person &x)const { return l*r < x.l*x.r; //乘积小的排在前面 } }; void multi(char tmp[],int x)//乘法 { int len= strlen(tmp),t,y; int k = 1,s = 0; memset(aim,'\0',sizeof(aim)); while(x) { t = x%10; y = 0; k = s; for(int i = len-1; i>=0; i--) { int p = (tmp[i]-'0')*t + y; if(aim[k]=='\0') aim[k] = '0'; y = (aim[k]-'0' + p)/10; aim[k] = (aim[k]-'0' + p)%10+'0'; k++; } if(y) aim[k++] = y+'0'; ++s; x /= 10; } for(int i = k-1,j = 0; i >= 0; i--) { tmp[j++] = aim[i]; } } void divs(char *tmp,int x)//除法 { int len = strlen(tmp); memset(c1,'\0',sizeof(c1)); int k = 0; int num = 0; for(int i = 0; i < len; i++) { num = num*10+(tmp[i]-'0'); if(num >= x) { c1[k] = num / x+'0'; num = num % x; } else { c1[k] = '0'; } k++; } int s = 0; while(c1[s]=='0') s++; memset(c2,'\0',sizeof(c2)); if(s==k) { c2[0] = '0'; } else { strcpy(c2,c1+s); } } bool cmp(char *a,char *b)//大数比较 { int lena = strlen(a),lenb = strlen(b); if(lena == lenb) { return strcmp(a,b)>0; } return lena > lenb; } int main() { //std::ios::sync_with_stdio(0); //cin.tie(0); int n; cin>>n; person a[n+2]; for(int i = 0; i <= n; i++) { cin>>a[i].l>>a[i].r; } sort(a+1,a+n+1); temp[0] = '1'; ans[0] = '0'; for(int i = 1; i <= n; i++) { multi(temp ,a[i-1].l); divs(temp,a[i].r); if(!cmp(ans,c2)) { strcpy(ans,c2); } } cout<

    推荐阅读


    上一篇：tarjan|POJ3694 Network

    下一篇：(python)常用数学字符(tcy)