您的位置: 首页  >  IT文章  >  [NOIP2012TG] 洛谷 P1080 国王游戏

[NOIP2012TG] 洛谷 P1080 国王游戏

分类: IT文章 • 2022-09-01 15:02:42

题意

给定两个等长序列(a[n],b[n])，与整数(a,b)。通过调换位置使

[max_{i=1}^{n}{iggllfloorfrac{(a imesprod_{j=1}^{i-1}a_i)}{b_i}iggr floor}quad (forall a_i,forall b_i inmathbb{N+}) ]

最小。

分析

从重新安排顺序容易看出，要求进行排序。这就要求我们用贪心思想分析题目，找到贪心的标准。

由冒泡排序的知识，容易得到邻项交换可使序列有序。
并且冒泡排序与快速排序效果相同，直接sort后求解即可。

所以我们利用贪心的常见思路：考虑只有两个元素的情况。当然，列式表达第i项与第i+1项效果相同，只是不便书写。

也就是说，两个元素(i,jquad(j=i+1))的大小关系可以拓展到任意(i,jquad(i<j))

引理

当(x>0)时：

  • (max(a,b) imes x=max(ax,bx))

非常易证。

证明

设元素分别为((a1,b1),(a2,b2))，奖金分别为(m,n)，有

[m=frac{a}{b_1} ]

[n=frac{a imes a_1}{b_2} ]

交换后为

[m'=frac{a}{b_2} ]

[n'=frac{a imes a_2}{b_1} ]

需要交换的条件是

[max(m,n)>max(m',n') ]

代入有

[max(frac{a}{b_1},frac{a imes a_1}{b_2})>max(frac{a}{b_2},frac{a imes a_2}{b_1}) ]

进一步化简

可有可无

两边同时乘(frac{b_1b_2}{a})

[max(b_2,a_1b_1)>max(b_1,a_2b_2) ]

  • 当(b_2<a_1b_1,b_1<a_2b_2)时
    ，直接比较(a_1b_1,a_2b_2)大小

  • 当(b_2>a_1b_1,b_1<a_2b_2)时
    ，必有(a_1b_1<b_2<a_2b_2)，等同于直接比较(a_1b_1,a_2b_2)

  • 当(b_2<a_1b_1,b_1>a_2b_2)时
    ，同上

  • 当(b_2>a_1b_1,b_1>a_2b_2)时
    无论(b_2,b_1)大小关系如何，都能由(a_1,a_2in mathbb{N+})推出矛盾。

综上所述，当

[a_1b_1>a_2b_2 ]

时，需要交换。

即按照(a_ib_i)升序排列。

代码

需要使用高精

这句话说着轻松，其实是这题调试的核心。。我习惯重载

#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN=1005,MAXDIGIT=5005;
int n,ak,bk;
struct LongInt
{
    short num[MAXDIGIT];
    int d;
};
struct person
{
    int a;
    int b;
}s[MAXN];
LongInt temp,ans;

inline LongInt read()
{
    LongInt temp,ret;
    temp.d=ret.d=0;
    char c=getchar();
    while(c<'0'||c>'9');
    while(c>='0'&&c<='9')
    {
        temp.num[++temp.d]=c-'0';
        c=getchar();
    }
    for(int i=temp.d;i>=1;i--)
        ret.num[++ret.d]=temp.num[i];
    return ret;
}

inline void write (LongInt x)
{
    for(int i=x.d;i>=1;i--)
        putchar(x.num[i]+'0');
}

LongInt operator + (LongInt n1,LongInt n2)
{
    LongInt ret;
    int len=max(n1.d,n2.d)+1;
    for(int i=1;i<=len;i++)
    {
        ret.num[i]=0;
        if(i<=n1.d)
            ret.num[i]+=n1.num[i];
        if(i<=n2.d)
            ret.num[i]+=n2.num[i];
        ret.num[i+1]+=(ret.num[i]/10);
        ret.num[i]%=10;
    }
    while(!ret.num[len]) len--;
    ret.d=len;
    return ret;
}

LongInt operator * (LongInt n1,LongInt n2)
{
    LongInt ret;
    int l1=n1.d,l2=n2.d;
    ret.d=n1.d+n2.d;
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
            ret.num[i+j-1]=0;
    for(int i=1;i<=l1;i++)
    {
        for(int j=1;j<=l2;j++)
        {
            ret.num[i+j-1]+=n1.num[i]*n2.num[j];
            ret.num[i+j]+=ret.num[i+j-1]/10;
            ret.num[i+j-1]%=10;
            
        }
    }
    while(!ret.num[ret.d]) ret.d--;
    return ret;
}

LongInt operator / (LongInt n1,int n2)
{
    int r=0,len=n1.d;
    for(int i=len;i>0;i--)
    {
        r*=10;
        r+=n1.num[i];
        n1.num[i]=r/n2;
        r%=n2;
    }
    while(!n1.num[n1.d]) n1.d--;
    return n1;
}

bool operator < (LongInt n1,LongInt n2)
{
     if(n1.d!=n2.d) return n1.d<n2.d;
     for(int i=n1.d;i>=1;i--)
          if(n1.num[i]!=n2.num[i]) return n1.num[i]<n2.num[i];
}

LongInt trans (int x)
{
    LongInt ret;
    ret.d=0;
    while(x)
    {
        ret.num[++ret.d]=x%10;
        x/=10;
    }
    return ret;
}

int comp(person p1,person p2)
{
    return p1.a*p1.b<p2.a*p2.b;
}

int main()
{
    scanf("%d",&n);
    scanf("%d%d",&ak,&bk);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&s[i].a,&s[i].b);
    sort(s+1,s+1+n,comp);
    temp=trans(ak);
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,temp/s[i].b);
        temp=temp*trans(s[i].a);
    }
    write(ans);
    return 0;
}

相关推荐