传送门:>Here<
题意:有$N$个大臣,第$i$个大臣的左手写着$a_i$,右手写着$b_i$。一个大臣得到的金币为$$所有排在他前面的大臣左手写的数字的乘积除以他自己右手的数字。问如何排列大臣们的顺序,使得到金币最多那个大臣得到的最少。$(n leq 10^3)$
解题思路
这是一个跟顺序有关的问题。顺序问题在OI内不好解决,在数据范围小的情况一般采用状压DP,在这样的问题中一般考虑贪心。
在顺序问题的贪心中,我们往往去考虑相邻的两个元素交换后答案的变化。即列出交换前和交换后的答案的表达式比较大小,使得交换后不比交换前优。得出的表达式就是排序的关键字了。事实上贪心严格的证明是要选取任意两个,但在推式子的时候很多时候选择相邻的两个会更好推,同时也能满足一样的性质。
于是在这道题中,我们设两个相邻的大臣$i,j$。设$a_i$的前缀积为$c_i$,则有:
交换前:前者得到$dfrac{c_{i-1}}{b_i}$,后者得到$dfrac{c_{j-1}}{b_j}$。
交换后:前者得到$dfrac{c_{i-1}}{b_j}$,后者得到$dfrac{a_jc_{j-1}}{a_ib_i}$
题目要求的是最大值最小,于是我们要令$max{dfrac{c_{i-1}}{b_i},dfrac{c_{j-1}}{b_j}} < max{dfrac{c_{i-1}}{b_j},dfrac{a_jc_{j-1}}{a_ib_i}}$
由于$c$是单调的,前面的第二项一定大于后面的第一项。因此问题转化为比较前后两者的第二项大小。
$dfrac{c_{j-1}}{b_j} < dfrac{a_jc_{j-1}}{a_ib_i}$,化简得$a_ib_i<a_jb_j$。这就是排序的关键字了。
Code
压位高精
/*This Program is written by QiXingZhi*/ #include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cassert> #include <iostream> #include <string> using namespace std; #define LL long long #define maxn 1010 #define base 10000 struct Bigint{ int c[2020],len; Bigint(){memset(c,0,sizeof(c));len=1;} void Zero(){while(c[len]==0&&len>1)len--;} Bigint Write(char* s){ memset(c,0,sizeof(c));len=1; int k=1,ll=strlen(s); for(int i=ll-1;i>=0;i--){ c[len]+=(s[i]-'0')*k; k*=10; if(k==base){ k=1,len++; } } Zero(); return *this; } void read(){ char s[10020]; scanf("%s",s); Write(s); } void Print(){ Zero(); printf("%d",c[len]); for(int i=len-1;i>=1;i--){ printf("%04d",c[i]); } } bool operator >(Bigint& b){ Zero();b.Zero(); if(len!=b.len)return len>b.len; for(int i=len;i>=1;i--){ if(c[i]!=b.c[i])return c[i]>b.c[i]; } return false; } bool operator <(Bigint& b){ Zero();b.Zero(); if(len!=b.len)return len<b.len; for(int i=len;i>=1;i--){ if(c[i]!=b.c[i])return c[i]<b.c[i]; } return false; } Bigint operator = (const int& b){ memset(c,0,sizeof(c)),len=1; char s[10020]; sprintf(s,"%d",b); Write(s); return *this; } Bigint operator *(const int & b){ Bigint r; r.len=len+4; for(int i=1;i<=r.len;i++){ r.c[i]+=c[i]*b; } for(int i=1;i<=r.len;i++){ r.c[i+1]+=r.c[i]/base; r.c[i]%=base; } r.Zero(); return r; } Bigint operator / (const int& b){ Bigint r,k; k=*this; r.len=len+1; for(int i=len;i>=1;i--){ r.c[i]=k.c[i]/b; if(i!=1)k.c[i-1]+=(k.c[i]%b*base); k.c[i]/=b; } r.Zero(); return r; } }; struct People{ int a,b; Bigint mul; }p[1010]; int N,A,B; Bigint ans,tot,x,y; inline bool cmp(const People& a, const People& b){ x = a.mul, y = b.mul; return x < y; } int main(){ scanf("%d",&N); scanf("%d %d",&A,&B); for(int i = 1; i <= N; ++i){ scanf("%d %d",&p[i].a,&p[i].b); p[i].mul = p[i].a * p[i].b; } sort(p+1,p+N+1,cmp); ans = 0; tot = A; for(int i = 1; i <= N; ++i){ if(tot/p[i].b > ans){ ans = tot/p[i].b; } tot = tot * p[i].a; } ans.Print(); return 0; }