1198 国王游戏

2012年NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 Description

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

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

输入描述 Input Description

第一行包含一个整数 n，表示大臣的人数。

第二行包含两个整数a和b，之间用一个空格隔开，分别表示国王左手和右手上的整数。

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

输出描述 Output Description

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

金币数。

样例输入 Sample Input

1 1

2 3

7 4

4 6

样例输出 Sample Output

数据范围及提示 Data Size & Hint

【输入输出样例说明】

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

【数据范围】

对于20%的数据，有1≤ n≤ 10，0 < a、b < 8；

对于40%的数据，有1≤ n≤20，0 < a、b < 8；

对于60%的数据，有1≤ n≤100；

对于60%的数据，保证答案不超过 10^9；

对于100%的数据，有 1 ≤ n ≤1,000，0 < a、b < 10000。

分类标签 Tags 点此展开

第一次裸搜

20分

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long 
#define N 10010
#define inf 1100000000
#define linf 999999999999999LL
inline const int read(){
    register int x=0,f=1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline const char in(){
    for(register char ch=getchar();;ch=getchar()) if((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')) return ch;
}
int n,a[N],sum[N];
int res,ans=0x7fffffff;
bool vis[N];
struct node{
    int l,r;
}d[N];
int top,s[N];
/*void check(){
    res=0;
    memset(sum,0,sizeof sum);
    sum[1]=d[0].l;
    for(int i=2;i<=n;i++) sum[i]=sum[i-1]*d[a[i-1]].l;
    for(int i=1;i<=n;i++) res=max(res,sum[i]/d[a[i]].r);
}
void dfs(int x){
    if(x==n+1){
        check();
        ans=min(ans,res);
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            vis[i]=1;
            a[x]=i;
            dfs(x+1);
            vis[i]=0;
        }
    }
}*/
void check(){
    res=0;
    memset(sum,0,sizeof sum);
    sum[1]=d[0].l;
    for(int i=2;i<=n;i++) sum[i]=sum[i-1]*d[s[i-1]].l;
    for(int i=1;i<=n;i++) res=max(res,sum[i]/d[s[i]].r);
}
void dfs(){
    s[top=1]=0;
    while(top>=1){
        if(top==n+1){
            /*for(int i=1;i<=n;i++)
                printf("%d ",s[i]);
            putchar('
');*/
            check();
            ans=min(ans,res);
            vis[s[--top]]=0;
            continue;
        }
        do
            s[top]++;
        while(vis[s[top]]&&s[top]<=n);
        if(s[top]<=n)
            vis[s[top]]=1,s[++top]=0;
        else
            vis[s[--top]]=0;
    }
}
inline bool cmp1(const node &a,const node &b){
    return a.l<b.l;
}
inline bool cmp2(const node &a,const node &b){
    return a.l>b.l;
}
int main(){
    srand(time(0));
    n=read();
    d[0].l=read();d[0].r=read();
    for(int i=1;i<=n;i++) d[i].l=read(),d[i].r=read();
    if(n<=10){
        //dfs(1);
        dfs();
        printf("%d
",ans);
        return 0;
    }
    sum[1]=d[0].l;
    sort(d+1,d+n+1,cmp1);
    for(int i=2;i<=n;i++) sum[i]=sum[i-1]*d[i-1].l;
    for(int i=1;i<=n;i++) res=max(res,sum[i]/d[i].r);
    ans=min(ans,res);res=0;
    sort(d+1,d+n+1,cmp2);
    for(int i=2;i<=n;i++) sum[i]=sum[i-1]*d[i-1].l;
    for(int i=1;i<=n;i++) res=max(res,sum[i]/d[i].r);
    ans=min(ans,res);
    for(int T=4;T--;){
        res=0;
        for(int i=1;i<=n;i++) a[i]=rand()%n+1;
        for(int i=2;i<=n;i++) sum[i]=sum[i-1]*d[a[i-1]].l;
        for(int i=1;i<=n;i++) res=max(res,sum[i]/d[a[i]].r);
        ans=min(ans,res);
    }
    printf("%d
",ans);
    return 0;
}

题解：

考虑交换相邻两个二元组的影响，交换i和i+1，实际上只影响到Fi和Fi+1。

设T = A1 * A2 * ... * Ai-2 * Ai-1

方案A：Fi = T / Bi，Fi+1 =T * Ai / Bi+1

方案B：Fi = T / Bi+1，Fi+1 =T * Ai+1 / Bi

①假设1 / Bi ＜ Ai / Bi+1，1 / Bi+1 ＜ Ai+1 / Bi

那么方案A优于方案B <=> Ai / Bi+1 ＜ Ai+1 / Bi <=> Ai * Bi ＜ Ai+1 * B i+1

②假设1 / Bi ≥ Ai / Bi+1 => Ai * Bi ≤ Bi+1

那么1 / Bi ≤ Ai+1 / Bi，方案A更优

③假设1 / Bi+1 ≥ Ai+1 / Bi => Ai+1 * Bi+1 ≤ Bi

那么1 / Bi+1 ≤ Ai / Bi+1，方案B更优

也就是说，对于相邻两个二元组，将A * B的较小的放在前面总能使答案更优。

已经按A * B排好序的方案为{1,2,3,4,...n}，发现可以通过一种构造，生成所有其他排列且保证结果更差。

假设任意一种排列是{P1,P2,P3,P4....Pn}，称为目标序列。{1,2,3,4,...n}，称为原始序列。我们观察目标序列，从后往前，每次将Pi从原始序列中往后交换直到它位于目标序列的位置。不难发现，序列在任意时刻都是由单调增的一段和排列好的一段组成，且每次交换都能保证结果更差。

综上，最优方案就是按A * B递增排序的方案，具体实现的时候需要加高精度处理。

这个做法的复杂度是O(NlogN+NL)。

60分代码（不加高精度）：

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
#define N 10010
struct node{
    ll a,b;
    bool operator < (const node &t) const{
        return a*b<t.a*t.b;
    }
}d[N];
ll n,ans,tot=1;
int main(){
    scanf("%lld",&n);
    scanf("%lld%lld",&d[0].a,&d[0].b);
    for(int i=1;i<=n;i++) scanf("%lld%lld",&d[i].a,&d[i].b);
    sort(d+1,d+n+1);
    for(int i=1;i<=n;i++){
        tot*=d[i-1].a;
        ans=max(ans,tot/d[i].b);
    }
    printf("%lld
",ans);
    return 0;
}

附point5

输入数据 (显示前20行)
100
70 94
43 9
92 18
18 9
86 31
24 32
46 49
23 69
40 56
27 75
28 85
37 29
99 80
44 70
14 9
30 38
46 32
93 87
42 49
35 60
99 73
57 8
38 35
73 33
6 32
10 36
78 75
49 98
50 48
91 78
18 3
86 24
18 84
27 28
83 25
15 95
38 18
50 89
79 9
3 17
1 52
74 32
76 99
24 36
9 43
93 7
65 27
36 84
75 31
94 44
33 2
85 5
42 18
4 33
45 84
92 87
86 34
36 44
61 59
59 28
1 97
60 23
9 64
96 47
57 100
90 7
54 93
17 30
71 23
72 32
14 95
48 40
27 15
92 78
52 11
93 21
56 60
22 47
21 58
89 11
29 13
36 14
95 91
47 12
16 36
19 80
19 92
73 68
66 1
53 97
13 60
83 5
63 99
98 37
2 67
84 95
26 60
63 33
2 78
91 38
9 31
你的答案
< 1622037442854406963
正确答案
> 2166489661101032350678866897536628698296804147316726878162441737980268621335310233327258927458239967674879428851028800069063620140885606400000000000000000

AC代码（60分代码+高精度处理=AC）：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ref(i,a,b) for(int i=a;i<=b;i++)
#define def(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
using namespace std;
typedef int arr[6005];
struct note{
    ll a,b,c;
}a[1005];
bool cmp(note x,note y){
    return x.c<y.c;
}
int n,bz;
arr sum,ans,t;
char s[5];
void divv(int x){
    int yu=0;
    memset(t,0,sizeof(t));
    def(i,sum[0],1){
        yu=yu*10+sum[i];
        if(yu>=x){
            if(!t[0]) t[0]=i;
            t[i]=yu/x;yu%=x;
        }
    }
}
void mx(){
    if(t[0]>ans[0]) memcpy(ans,t,sizeof(ans));
    else if(ans[0]==t[0]){
        def(i,ans[0],1) 
            if(t[i]>ans[i]){
                memcpy(ans,t,sizeof(ans));
                return;
            } 
            else if(ans[i]<t[i]) return;
    }
}
void cheng(int x){
    arr t;
    memset(t,0,sizeof(t));
    ref(i,1,sum[0]){
        t[i]=t[i]+sum[i]*x;t[i+1]+=t[i]/10;t[i]%=10;
    }
    for(t[0]=sum[0];t[t[0]+1];) t[++t[0]+1]+=t[t[0]]/10,t[t[0]]%=10;
    memcpy(sum,t,sizeof(sum));
}
int main(){
    freopen("sh.txt","r",stdin);
    scanf("%d",&n);scanf("%s",s+1);
    def(i,strlen(s+1),1) sum[++sum[0]]=s[i]-'0';
    scanf("%d",&bz);
    ref(i,1,n) scanf("%lld%lld",&a[i].a,&a[i].b),a[i].c=a[i].a*a[i].b;
    sort(a+1,a+n+1,cmp);
    ref(i,1,n){
        divv(a[i].b);
        mx();
        cheng(a[i].a);
    }
    def(i,ans[0],1) printf("%d",ans[i]);
    return 0;
}