题解 | 国王的游戏-NOIP2012提高组复赛E题

输入描述:

题目分析：

我们对于国王身后的两个点来分析

队列可能是这样的：

*	Left	Right
king:
p1
p2

那么我们计算可得

队列也有可能是这样的

*	Left	Right
king:
p2
p1

那么我们计算可得

我们来对比一下两个答案：

可以替换得：

显然我们可以得到:

即：

如果

那么易得：

即： 

变形可得：

当时，我们也能够得到的结论

所以，为了取到最小值，我们需要将较小的放在前面

那么我们以为关键字排序即可

同时，统计答案时一定不要忘了写高精度！

更新!

最近有一位dalao私信了我@Zory,提出了他的问题

Q:对于一个方案,a和b的调换,可能会影响到中间的数结果,怎么办?

A:让我们再来看一看

已知在国王后面的两个点a*ba∗b 较小的应该放在前面,那么将国王左手的a_0a0看做一段序列的乘积AA,则又变成了这样的形式:

*	Left	Right
king:
p1
p2

对于这两个人来说,根据他们的排列,会贡献两种答案和,我们已经分析过应该怎么排才能取到

这就相当于对于相邻的两个点来说(先不管别的点怎么排), 较小的应该放在前面

这样,本来确定的在国王后面的两个点就被推广为了所有点对,根据冒泡排序你的智慧,很容易的发现将所有的点对以较小的放在前面会使总答案最小

Q:但是我还是不懂为什么点对位置的调换不会影响其他的答案呢?

A:在一段序列后面的两对点不管怎么掉换都不会影响前面那段序列的答案,并且,也不会影响后面序列的答案!

看看关系式,对于前面的序列的答案,根本就后面的点对没关系

对于后面的点对,他们的答案之和前面点的左手乘积和有关

那我将相邻两个点进行掉换,是不是有没有影响两个点前面的序列,又没有影响两个点后面的序列呢?

同时,它还将这两个点所贡献的答案取到了较小值

那么对于每个点对我们都这么做,掉换的不是当前点对时没影响,而且交换的点对的答案都减小了,那么最终能取到全局最优!(无法掉换以得到更优解)

Q:为什么你证明的是冒泡的方式答案会不断减小,而程序中用的是快排呢?

A:我们证明,当取到最小值时,对于相邻两对数上面的乘积必然要小于下面的乘积,对于整体来说,不就是上面的乘积最小,下面的乘积最大么?

也就是说我们用冒泡的方式证明了乘积的有序性,而使用快排来实现而已

你懂了么?

PS:压位更快(懒)

Code

#include <bits/stdc++.h>
using namespace std;
int now[20010],sum[20010],ans[20010],add[20010];
struct Node {
    int a;
    int b;
    long long a_b;
}node[1010];
int read() {
    int ans=0,flag=1;
    char ch=getchar();
    while( (ch>'9' || ch<'0') && ch!='-' ) ch=getchar();
    if(ch=='-') flag=-1,ch=getchar();
    while(ch>='0' && ch<='9') ans=ans*10+ch-'0',ch=getchar();
    return ans*flag;
}
void times(int x) {
    memset(add,0,sizeof(add));
    for(int i=1;i<=ans[0];i++) {
        ans[i]=ans[i]*x;
        add[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    for(int i=1;i<=ans[0]+4;i++) {
        ans[i]+=add[i];
        if(ans[i]>=10) {
            ans[i+1]+=ans[i]/10;
            ans[i]%=10;
        }
        if(ans[i]!=0) {
            ans[0]=max(ans[0],i);
        } 
    }
    return ;
}
int divition(int x) {
    memset(add,0,sizeof(add));
    int q=0;
    for(int i=ans[0];i>=1;i--) {
        q*=10;
        q+=ans[i];
        add[i]=q/x;
        if(add[0]==0 && add[i]!=0) {
            add[0]=i;
        }
        q%=x; 
    }
    return 0;
}
bool compare() {
    if(sum[0]==add[0]) {
        for(int i=add[0];i>=1;i--) {
            if(add[i]>sum[i]) return 1;
            if(add[i]<sum[i]) return 0;
        }
    }
    if(add[0]>sum[0]) return 1;
    if(add[0]<sum[0]) return 0;
}
void cp () {
    memset(sum,0,sizeof(sum));
    for(int i=add[0];i>=0;i--) {
        sum[i]=add[i];
    }
    return ;
}
bool cmp(Node a,Node b) {
    return a.a_b<b.a_b;
}
int main() {
    int n=read();
    for(int i=0;i<=n;i++) {
        node[i].a=read(),node[i].b=read();
        node[i].a_b=node[i].a*node[i].b;
    }
    sort(node+1,node+n+1,cmp);
    ans[0]=1,ans[1]=1;
    for(int i=1;i<=n;i++) {
        times(node[i-1].a);
        divition(node[i].b);
        if(compare()) {
            cp();
        }
    }
    for(int i=sum[0];i>=1;i--)
        printf("%d",sum[i]);
    return 0;
}