【noip】国王游戏 贪心 高精度

本文主要是介绍【noip】国王游戏 贪心 高精度，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

说实话我一开始是不想发这道题的，虽然比较水，但不知道是不是因为我太久都没有写高精度了，还是写错了，才40分，还是发上来吧。

描述

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

输入格式

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

输出格式

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

样例

样例输入

3
1 1
2 3
7 4
4 6

样例输出

2

限制

每个测试点1s

提示

对于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 < a、b < 10000。

来源

Noip2012提高组复赛Day1T2

这道题没什么说的，就是以来可以看出是贪心，但是不好直接看出贪心的正确性，这里就简单地说一下。
首先我们贪心很简单，就是直接按照左右手的乘积由小到大排序，最后的人左右手成绩最大
我们可以这样来考虑：现在一共有x人等着我们排序我们设所有人的左手乘积 $mulit(x)=\prod_{i=1}^x{left(i)}$那么最后一个人的值就是$\frac{mulit(x)}{left(x)*right(x)}$所以我们就直接按照成绩来排序就可以了
然后mulit（x）用高精度算就可以了，没什么好多说的了，直接放代码了
代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define M 10005using namespace std;struct hp
{int n[M]; 
}mul,mx;struct person
{int a,b,mu;
}p[M];bool com(const person &a,const person &b)
{return a.mu<b.mu;
}bool cmp(hp a,hp b)
{if(a.n[0]>b.n[0])return 1;for(int i=a.n[0];i>=1;i--){if(a.n[i]>b.n[i])return 1;if(b.n[i]>a.n[i])return 0;}return 0;
}void mulit(hp &a,int b)
{for(int i=1;i<=a.n[0];i++)a.n[i]*=b;for(int i=1;i<=a.n[0]-1;i++){a.n[i+1]+=a.n[i]/10;a.n[i]%=10;}while(a.n[a.n[0]]>=10){a.n[a.n[0]+1]=a.n[a.n[0]]/10;a.n[a.n[0]]%=10;a.n[0]++;}
}hp chu(hp a,int b)
{for(int i=a.n[0];i>=1;i--){if(i!=1)a.n[i-1]+=(a.n[i]%b)*10;a.n[i]/=b;}while(a.n[a.n[0]]==0)a.n[0]--;return a;
}int n;int main()
{freopen("game.in","r",stdin);freopen("game.out","w",stdout);cin>>n;int a,b;cin>>a>>b;mul.n[0]=1;mul.n[1]=a;for(int i=1;i<=n;i++){scanf("%d%d",&p[i].a,&p[i].b);p[i].mu=p[i].a*p[i].b;}sort(p+1,p+1+n,com);for(int i=1;i<=n;i++){hp temp=chu(mul,p[i].b);if(cmp(temp,mx))mx=temp;mulit(mul,p[i].a);}for(int i=mx.n[0];i>=1;i--)printf("%d",mx.n[i]);return 0;
}

大概就是这个样子，如果有什么问题，或错误，请在评论区提出，谢谢。

这篇关于【noip】国王游戏 贪心 高精度的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---