MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » Luogu 1080 【NOIP2012】国君游戏 (贪心,高精度)

Luogu 1080 【NOIP2012】国君游戏 (贪心,高精度)

www.MyException.Cn  网友分享于:2013-10-27  浏览:0次
Luogu 1080 【NOIP2012】国王游戏 (贪心,高精度)

Luogu 1080 【NOIP2012】国王游戏 (贪心,高精度)

Description

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

Input

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

Output

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

Sample Input

3
1 1
2 3
7 4
4 6

Sample Output

2

Http

Luogu:https://www.luogu.org/problem/show?pid=1080

Source

贪心,高精度

题目大意

给出若干组二元组(a,b),对于一种排列方式,定义第i个二元组的花费为前面所有人的a之积除以第i个的b。现在要求求一种排列方式,使得其中最大的花费最小。

解决思路

我们来考虑排序方式。对于\(\forall\)两个人\(A,B\),设\(A\)的左手为\(A_l\),右手为\(A_r\)\(B\)同理。现在假设\(A与B\)是相邻的,他们前面的所有人的左手乘积为\(P\)。则有

顺序 A的花费 B的花费
A在前 \(\frac{T}{A_r}\) \(\frac{T*A_l}{B_r}\)
B在前 \(\frac{T*B_l}{A_r}\) \(\frac{T}{B_r}\)

那么我们如何排列\(A和B\)呢?那一定取决于上面表格中的两行中的最大值。而因为所有的数都是整数,所以我们可以知道\(\frac{T}{A_r}\)\(\frac{T}{B_r}\)是不可能成为最大值的。
所以我们考虑\(\frac{T*A_l}{B_r}\)\(\frac{T*B_l}{A_r}\)
\(\frac{T*A_l}{B_r} > \frac{T*B_l}{A_r}\)时,经过恒等变换,我们可以得到\(A_l*A_r>B_l*B_r\)也就是说,当A的左右手乘积大于B的左右手乘积时,我们把B排在前面会更优。
那么\(\frac{T*A_l}{B_r} < \frac{T*B_l}{A_r}\)是否也满足呢?我们发现是满足的。
也就是说,最优的排列方式为将人按照左右手乘积升序排序。至于求解其中的最大值,只要从1开始做一遍就可以啦。
最后需要注意的是,本题需要高精度。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=2000;
const int maxNum=5000;
const int inf=2147483647;

#define ll long long

class People//定义一个关于人的结构体,方便按照左右手乘积排序
{
public:
    ll l,r;
};

bool operator < (People A,People B)//定义比较
{
    return A.l*A.r<B.l*B.r;
}

class BigInteger//定义高精度
{
public:
    int siz;
    ll Num[maxNum];
    BigInteger();
    BigInteger(int x);
    BigInteger(ll x);
    void operator = (int B);
    bool operator == (int B);
    bool operator == (BigInteger B);
    BigInteger operator + (BigInteger B);
    BigInteger operator * (ll B);
    BigInteger operator / (ll B);
};

ostream& operator << (ostream & os,BigInteger A)//重载输出运算符方便输出
{
    if (A.siz==0)
    {
        os<<0;
        return os;
    }
    for (int i=A.siz;i>=1;i--)
        os<<A.Num[i];
    return os;
}


bool operator < (BigInteger A,BigInteger B)//重载小于运算符
{
    if (A.siz<B.siz)
        return 1;
    if (A.siz>B.siz)
        return 0;
    for (int ii=A.siz;ii>=1;ii--)
    {
        if (A.Num[ii]>B.Num[ii])
            return 0;
        if (A.Num[ii]<B.Num[ii])
            return 1;
    }
}

ll n;
People P[maxN];

ll read();

int main()//主程序
{
    n=read();
    P[0].l=read();
    P[0].r=read();
    for (int i=1;i<=n;i++)
    {
        P[i].l=read();
        P[i].r=read();
    }
    sort(&P[1],&P[n+1]);//将人排序
    BigInteger ret=P[0].l;//ret即前面所有人左手的乘积
    BigInteger Ans=0;//Ans记录最大的
    for (int i=1;i<=n;i++)//依次计算
    {
        Ans=max(Ans,ret/P[i].r);
        ret=ret*P[i].l;
    }
    cout<<Ans<<endl;
    return 0;
}

ll read()
{
    ll x=0;
    char ch=getchar();
    while ((ch<'0')||(ch>'9'))
        ch=getchar();
    while ((ch>='0')&&(ch<='9'))
    {
        x=x*10+ch-48;
        ch=getchar();
    }
    return x;
}
//以下就是高精度的重载
BigInteger::BigInteger()
{
    siz=0;
    mem(Num,0);
}

BigInteger::BigInteger(int B)
{
    siz=0;
    mem(Num,0);
    while (B!=0)
    {
        siz++;
        Num[siz]=B%10;
        B=B/10;
    }
}

BigInteger::BigInteger(ll B)
{
    siz=0;
    mem(Num,0);
    while (B!=0)
    {
        siz++;
        Num[siz]=B%10;
        B=B/10;
    }
}

void BigInteger::operator = (int B)
{
    siz=0;
    mem(Num,0);
    while (B!=0)
    {
        siz++;
        Num[siz]=B%10;
        B=B/10;
    }
}

bool BigInteger::operator == (BigInteger B)
{
    if (siz!=B.siz)
        return 0;
    for (int ii=1;ii<=siz;ii++)
        if (Num[ii]!=B.Num[ii])
            return 0;
    return 1;
}

bool BigInteger::operator == (int B)
{
    BigInteger A(B);
    if (A==B)
        return 1;
    return 0;
}

BigInteger BigInteger::operator + (BigInteger B)
{
    BigInteger Ans;
    Ans.siz=max(siz,B.siz);
    for (int ii=1;ii<=Ans.siz;ii++)
        Ans.Num[ii]=Num[ii]+B.Num[ii];
    for (int ii=1;ii<Ans.siz;ii++)
    {
        Ans.Num[ii+1]+=Ans.Num[ii]/10;
        Ans.Num[ii]%=10;
    }
    while (Ans.Num[Ans.siz]>=10)
    {
        Ans.Num[Ans.siz+1]+=Ans.Num[Ans.siz]/10;
        Ans.Num[Ans.siz]%=10;
        Ans.siz++;
    }
    return Ans;
}

BigInteger BigInteger::operator * (ll B)
{
    BigInteger Ans;
    for (int ii=1;ii<=siz;ii++)
        Ans.Num[ii]=1ll*Num[ii]*(ll)(B);
    Ans.siz=siz;
    for (int ii=1;ii<Ans.siz;ii++)
    {
        Ans.Num[ii+1]+=Ans.Num[ii]/10;
        Ans.Num[ii]%=10;
    }
    while (Ans.Num[Ans.siz]>=10)
    {
        Ans.Num[Ans.siz+1]+=Ans.Num[Ans.siz]/10;
        Ans.Num[Ans.siz]%=10;
        Ans.siz++;
    }
    return Ans;
}

BigInteger BigInteger::operator / (ll B)
{
    BigInteger Ans;
    int res=0;
    for (int ii=siz;ii>=1;ii--)
    {
        res=res*10+Num[ii];
        Ans.Num[ii]=res/B;
        res=res%B;
    }
    Ans.siz=siz;
    while (Ans.Num[Ans.siz]==0)
        Ans.siz--;
    return Ans;
}

文章评论

“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
每天工作4小时的程序员
每天工作4小时的程序员
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
程序员都该阅读的书
程序员都该阅读的书
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
程序员的鄙视链
程序员的鄙视链
我的丈夫是个程序员
我的丈夫是个程序员
那些性感的让人尖叫的程序员
那些性感的让人尖叫的程序员
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
 程序员的样子
程序员的样子
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
程序员必看的十大电影
程序员必看的十大电影
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
代码女神横空出世
代码女神横空出世
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
Java程序员必看电影
Java程序员必看电影
程序员应该关注的一些事儿
程序员应该关注的一些事儿
如何成为一名黑客
如何成为一名黑客
漫画:程序员的工作
漫画:程序员的工作
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
中美印日四国程序员比较
中美印日四国程序员比较
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
鲜为人知的编程真相
鲜为人知的编程真相
编程语言是女人
编程语言是女人
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
程序员和编码员之间的区别
程序员和编码员之间的区别
我是如何打败拖延症的
我是如何打败拖延症的
一个程序员的时间管理
一个程序员的时间管理
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
老程序员的下场
老程序员的下场
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
旅行,写作,编程
旅行,写作,编程
那些争议最大的编程观点
那些争议最大的编程观点
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
10个调试和排错的小建议
10个调试和排错的小建议
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有