题解 P1080 【国王游戏】
League丶翎
2017-11-05 21:41:36
**题目分析：**
我们对于国王身后的两个点来分析
队列可能是这样的：
| \* | Left | Right |
| --------| -----: | :----: |
| king: | $a_0$ | $b_0$ |
| p1 | $a_1$ | $b_1$ |
| p2 | $a_2$ | $b_2$ |
那么我们计算可得$ans_1$=$max(\frac{a_0}{b_1},\frac{a_0*a_1}{b_2})$
队列也有可能是这样的
| \* | Left | Right |
| --------| -----: | :----: |
| king: | $a_0$ | $b_0$ |
| p2 | $a_2$ | $b_2$ |
| p1 | $a_1$ | $b_1$ |
那么我们计算可得$ans_2$=$max(\frac{a_0}{b_2},\frac{a_0*a_2}{b_1})$
我们来对比一下两个答案：
$ans_1$=$max(\frac{a_0}{b_1},\frac{a_0*a_1}{b_2})$
$ans_2$=$max(\frac{a_0}{b_2},\frac{a_0*a_2}{b_1})$
可以替换得：
$ans_1$=$max(k_1,k_2)$
$ans_2$=$max(k_3,k_4)$
显然我们可以得到:
$\frac{a_0*a_1}{b_2}$>$\frac{a_0}{b_2}$
$\frac{a_0*a_2}{b_1}$>$\frac{a_0}{b_1}$
即：
$k_2$>$k_3$
$k_4$>$k_1$
如果$ans_1$<$ans_2$
那么易得：
$k_4>k_2$
即：
$\frac{a_0*a_2}{b_1}$>$\frac{a_0*a_1}{b_2}$
变形可得：
$a_1*b_1<a_2*b_2$
当$a_1*b_1<a_2*b_2$时，我们也能够得到$ans_1$<$ans_2$的结论
所以，为了$ans$取到最小值，我们需要将$a_i*b_i$较小的放在前面
那么我们以$a_i*b_i$为关键字排序即可
同时，统计答案时一定**不要忘了写高精度！**
## 更新!
最近有一位dalao私信了我[@Zory](https://www.luogu.org/space/show?uid=30058),提出了他的问题
Q:对于一个方案,a和b的调换,可能会影响到中间的数结果,怎么办?
A:让我们再来看一看
已知在国王后面的两个点$a*b$ 较小的应该放在前面,那么将国王左手的$a_0$看做一段序列的乘积$A$,则又变成了这样的形式:
| \* | Left | Right |
| --------| -----: | :----: |
| king: | $A$ | |
| p1 | $a_1$ | $b_1$ |
| p2 | $a_2$ | $b_2$ |
对于这两个人来说,根据他们的排列,会贡献两种答案$ans1$和$ans2$,我们已经分析过应该怎么排才能取到$min(ans1,ans2)$
这就相当于对于相邻的两个点来说(先不管别的点怎么排),$a*b$ 较小的应该放在前面
这样,本来确定的在国王后面的两个点就被推广为了所有点对,根据~~冒泡排序~~你的智慧,很容易的发现将所有的点对以$a*b$**较小的放在前面**会使总答案最小
Q:但是我还是不懂为什么点对位置的调换不会影响其他的答案呢?
A:在一段序列后面的两对点**不管怎么掉换都不会影响前面那段序列的答案,并且,也不会影响后面序列的答案!**
看看关系式,对于前面的序列的答案,根本就后面的点对没关系
对于后面的点对,他们的答案之和前面点的左手乘积和有关
那我将相邻两个点进行掉换,是不是有没有影响两个点前面的序列,又没有影响两个点后面的序列呢?
同时,它还将这两个点所贡献的答案取到了较小值$min(ans1,ans2)$
那么对于每个点对我们都这么做,掉换的不是当前点对时没影响,而且交换的点对的答案都减小了,那么最终能取到全局最优!(无法掉换以得到更优解)
Q:为什么你证明的是冒泡的方式答案会不断减小,而程序中用的是快排呢?
A:我们证明,当取到最小值时,对于相邻两对数上面的乘积必然要小于下面的乘积,对于整体来说,不就是上面的乘积最小,下面的乘积最大么?
也就是说我们**用冒泡的方式证明了乘积的有序性,而使用快排来实现而已**
你懂了么?
PS:压位更快(懒)
**Code**
```cpp
#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;
}
```