NOIP2012国王游戏(贪心+高精度)

逃离我推掉我的手 2021-09-15 23:02 310阅读 0赞

## 0701 国王游戏  ##

描述

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

输入格式

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

输出格式

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

样例输入

3
    1 1
    2 3
    7 4
    4 6

样例输出

数据范围与约定

对于 20%的数据,有 1≤ n≤ 10,0 < a、b < 8;  
对于 40%的数据,有 1≤ n≤20,0 < a、b < 8;  
对于 60%的数据,有 1≤ n≤100;  
对于 60%的数据,保证答案不超过 109;  
对于 100%的数据,有 1 ≤ n ≤1,000,0 < a、b < 10000。

样例解释

按 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。

来源

CCF NOIP2012 D1T2

按照每个大臣左右手的乘积从小到大排序，就是最优的排队方案，这个贪心的正确性可以用临项交换证明。

推了半天，这里直接给结论。

在任何情况下，减小逆序对数不会造成整体结果变差，增加逆序对数不会造成整体结果变好。

即当逆序对数为0时(排序后)，方案为最优策略。

然后再贴个大数模板，就可以过了

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    const int maxn = 1100;
    
    struct pe
    {
    	int a,b;
    	ll x;
    } p[maxn];
    
    bool operator < (const pe &a,const pe &b)
    {
    	return a.x < b.x;
    }
    struct num{int s,a[1100];} ans,now,temp;
    
    bool operator < (num a,num b)
    {
    	if(a.s < b.s) return 1;
    	if(a.s > b.s) return 0;
    	for(int i = a.s;i;i--)
    	{
    		if(a.a[i]<b.a[i]) return 1;
    		if(a.a[i]>b.a[i]) return 0;
    	}
    }
    num operator *(num a,int b)
    {
    
        num c; int i,jin=0;
        memset(&c,0,sizeof(c));
        for(i=1;i<=a.s;i++)
        {
            jin+=a.a[i]*b;
            c.a[i]=jin%10000;
            jin/=10000;
        }
        c.s=a.s;
        while(jin) c.a[++c.s]=jin%10000,jin/=10000;
        return c;
    }
    
    num operator /(num a,int b)
    {
        num c; int i,rest=0;
        memset(&c,0,sizeof(c));
        for(i=a.s;i;i--)
        {
            rest=rest*10000+a.a[i];
            c.a[i]=rest/b;
            rest%=b;
        }
        c.s=a.s;
        while(c.s>1&&!c.a[c.s]) c.s--;
        return c;
    }
    
    int n;
    int s,k;
    int main()
    {
    	cin>>n;
       cin>>p[0].a>>p[0].b;
    	rep(i,1,n+1)
    	{
    		cin>>p[i].a>>p[i].b;
    		p[i].x = p[i].a*p[i].b;
    	}
    	sort(p+1,p+n+1);
    	now.s = now.a[1] = ans.s = 1;
    	rep(i,1,n+1)
    	{
    		 now=now*p[i-1].a;
            temp=now/p[i].b;
            if(ans<temp) ans=temp;
    	}
    	 printf("%d",ans.a[ans.s]);
        for(int i=ans.s-1;i;i--) printf("%04d",ans.a[i]);
        puts("");
    }