问题描述

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

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

输入格式

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

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

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

输出格式

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

样例输入

3

1 1

2 3

7 4

4 6

样例输出

2

样例说明

按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%的数据，保证答案不超过1≤n≤1,000,0<a,b<10000。

NOIP 2012 提高组 第一天 第二题

题解

假设队伍已经排好，对于其中相邻的两个位置i，j（i=j-1），这两个位置的人分别为x，y，x能排在i位置，y排在j位置的条件是交换x，y的位置（即令x排在j，y排在i）后j位置上的人（y）获得的奖赏比交换x，y位置前（x在i，y在j）j位置上的人（x）获得的奖赏少（不需要考虑i位置，因为i位置在这之前和i-1一起考虑了），设i位置前所有人左手的乘积为s，则

   s*x左手/y右手 < s*y左手/x右手

化简得

   x左手*x右手 < y左手*y右手

所以按两手乘积从小到大排序即为队伍顺序

手上的数字最大为10⁴，而人数最多为10³，那么计算结果最大能达到（10⁴）^10³ =10⁴⁰⁰⁰，即最大有4000位数，即使是long long也显得很渺小，所以别忘了用上高精度

 1 #include <algorithm>
 2 #include <cstring>
 3 #include <cstdio>
 4 #define ll long long
 5 int n;
 6 struct note{
 7     int v[10000],len;
 8 }s,ans;
 9 struct node{
10     int l,r;
11     ll v;
12 }a[1005];
13 bool cmp(node x,node y)
14 {
15     return x.v<y.v;
16 }
17 note operator * (note a,int b)
18 {
19     int lena=a.len,lenc=lena,i,w=0;
20     note c;
21     memset(c.v,0,sizeof(c.v));
22     for (i=1;i<=lena;i++)
23       c.v[i]=a.v[i]*b+w,
24       w=c.v[i]/10000,
25       c.v[i]%=10000;
26     for (;w;c.v[++lenc]=w%10000,w/=10000);
27     c.len=lenc;
28     return c;
29 }
30 note operator / (note a,int b)
31 {
32     int i,lena=a.len,lenc=1,x=0;
33     note c;
34     for (i=lena,x=a.v[lena];x<b && i>1;x=x*10000+a.v[--i]);
35     c.v[1]=x/b;  x%=b;
36     for (i--;i>=1;i--)
37       x=x*10000+a.v[i],
38       c.v[++lenc]=x/b,
39       x%=b;
40     for (i=1;i<=lenc/2;i++)
41       c.v[i]^=c.v[lenc-i+1],
42       c.v[lenc-i+1]^=c.v[i],
43       c.v[i]^=c.v[lenc-i+1];
44     c.len=lenc;
45     return c;
46 }
47 bool operator > (note a,note b)
48 {
49     if (a.len<b.len) return 0;
50     if (a.len>b.len) return 1;
51     int len=a.len,i;
52     for (i=len;i>=1;i--)
53       if (a.v[i]>b.v[i]) return 1; 
54       else if (a.v[i]<b.v[i]) return 0;
55     return 0;
56 }
57 void Print_(note x)
58 {
59     int len=x.len,i;
60     printf("%d",x.v[len]); 
61     for (i=len-1;i>=1;i--)
62       printf("%04d",x.v[i]);
63     return;
64 }
65 int main()
66 {
67     int i,j;
68     note x;
69     scanf("%d",&n);
70     for (i=0;i<=n;i++)
71       scanf("%d%d",&a[i].l,&a[i].r),
72       a[i].v=a[i].l*a[i].r;
73     std::sort(a+1,a+n+1,cmp);
74     //s=a[0].l;
75     {
76         int len=0,b=a[0].l;
77         while (b)
78           s.v[++len]=b%10000,
79           b/=10000;
80         s.len=len;
81         for (int i=1;i<=len/2;i++)
82           s.v[i]^=s.v[len-i+1],
83           s.v[len-i+1]^=s.v[i],
84           s.v[i]^=s.v[len-i+1];
85     }
86 
87     for (i=1;i<=n;i++)
88     {
89         x=s/a[i].r;
90         if (x>ans) ans=x;
91         s=s*a[i].l;
92     } 
93     Print_(ans);
94     return 0;
95 }