【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)=∏xi=1left(i) 那麼最後一個人的值就是 mulit(x)left(x)∗right(x) 是以我們就直接按照成績來排序就可以了

然後mulit（x）用高精度算就可以了，沒什麼好多說的了，直接放代碼了

代碼如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define M 10005

using 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[]>b.n[])return ;
    for(int i=a.n[];i>=;i--)
    {
        if(a.n[i]>b.n[i])return ;
        if(b.n[i]>a.n[i])return ;
    }
    return ;
}

void mulit(hp &a,int b)
{
    for(int i=;i<=a.n[];i++)a.n[i]*=b;
    for(int i=;i<=a.n[]-;i++)
    {
        a.n[i+]+=a.n[i]/;
        a.n[i]%=;
    }
    while(a.n[a.n[]]>=)
    {
        a.n[a.n[]+]=a.n[a.n[]]/;
        a.n[a.n[]]%=;
        a.n[]++;
    }
}

hp chu(hp a,int b)
{
    for(int i=a.n[];i>=;i--)
    {
        if(i!=)a.n[i-]+=(a.n[i]%b)*;
        a.n[i]/=b;
    }
    while(a.n[a.n[]]==)a.n[]--;
    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[]=;
    mul.n[]=a;
    for(int i=;i<=n;i++)
    {
        scanf("%d%d",&p[i].a,&p[i].b);
        p[i].mu=p[i].a*p[i].b;
    }
    sort(p+,p++n,com);
    for(int i=;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[];i>=;i--)printf("%d",mx.n[i]);
    return ;
}
           

大概就是這個樣子，如果有什麼問題，或錯誤，請在評論區提出，謝謝。