「NOIP 2012」国王游戏

发表于 | | 阅读次数:
字数统计: 947 字

Description

题目链接：Luogu 1080

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

数据范围：$1\le n\le 10^3$，$0<a,b<10^4$

Solution

我们可以发现，对于第 $i$ 和 $i+1$ 两个人，他们的先后对其他人没有影响，所以我们可以通过调整 $i$ 和 $i+1$ 的位置，以这样的局部最优解获得全局最优解。

设第 $i$ 个人左手的数字为 $a_i$，右手的数字为 $b_i$，第 $i$ 个人之前（不包括第 $i$ 个人）的人左手数字之积为 $p$。对于 $i$ 和 $j$（我们令 $j=i+1$）的前后有两种可能。

情况 $1$：$i$ 在 $j$ 的前面 情况 $2$：$i$ 在 $j$ 的后面
前面为 $i$ 后面为 $j$ 答案 前面为 $j$ 后面为 $i$ 答案
$a_i$ $a_j$ $\max(\frac{p}{b_i},\frac{p\times a_i}{b_j})$ $a_j$ $a_i$ $\max(\frac{p}{b_j},\frac{p\times a_j}{b_i})$
$b_i$ $b_j$ $b_j$ $b_i$

然后我们对比一下两个答案：

如果此时我们要求 $i$ 在 $j$ 的前面，那么需要满足 $ans_1<ans_2$ 即 $\max(\frac{p}{b_i},\frac{p\times a_i}{b_j})<\max(\frac{p}{b_j},\frac{p\times a_j}{b_i})$。

由于 $\frac{p}{b_i}<\frac{p\times a_j}{b_i}$且 $\frac{p}{b_j}<\frac{p\times a_i}{b_j}$，所以如果要满足 $ans_1<ans_2$，那么一定有 $\frac{p\times a_i}{b_j}<\frac{p\times a_j}{b_i}$，变形可得 $a_i\times b_i<a_j\times b_j$，所以我们只需要以 $a_i\times b_i$ 为关键字从小到大排序即可。最后求解时套上高精度。我菜死了高精度调了一个晚上

时间复杂度：$O(n^2)$（朴素的高精度）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
 
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N=1e3+5;
int n;
struct data {
    int x,y;
    bool operator < (const data &rhs) const {
        return x*y<rhs.x*rhs.y;
    }
} a[N];
struct huge {
    int len,a[4005];
    huge(int x=0) {memset(a,0,sizeof(a)),a[len=1]=x;}
    huge operator * (const int &x) const {
        huge c;
        for(int i=1;i<=len;++i) c.a[i]=a[i]*x;
        c.len=len+4;
        for(int i=1;i<=c.len;++i) c.a[i+1]+=c.a[i]/10,c.a[i]%=10;
        while(!c.a[c.len]) --c.len;
        return c;
    }
    huge operator / (const int &x) const {
        huge c;
        c.len=len;
        memset(c.a,0,sizeof(c.a));
        int r=0;
        for(int i=len;i;--i) r=10*r+a[i],c.a[i]=r/x,r%=x;
        while(c.len>1&&!c.a[c.len]) --c.len;
        return c;
    }
    bool operator < (const huge &b) const {
        if(len!=b.len) return len<b.len;
        for(int i=len;i;--i) if(a[i]!=b.a[i]) return a[i]<b.a[i];
        return 0;
    }
    void print() {
        for(int i=len;i;--i) printf("%d",a[i]);
        puts("");
    }
};

int main() {
    scanf("%d",&n);
    for(int i=0;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
    std::sort(a+1,a+n+1);
    huge prod(1),ans;
    for(int i=1;i<=n;++i) {
        prod=prod*a[i-1].x;
        huge now=prod/a[i].y;
        if(ans<now) ans=now;
    }
    ans.print();
    return 0;
}
0%