P1080 [NOIP2012 提高组] 国王游戏 题解

small_lemon_qwq · 2024-06-20 18:12:07 · 题解

\colorbox{orange}{\color{white}\texttt{题目传送门}}

这题显然是排序，我们考虑第 x 大臣与 x+1 大臣什么时候需要交换。

我们假设 a_i 表示第 i 个大臣左手上的数，b_i 表示第 i 个大臣右手上的数，a_0 和 b_0 表示国王左右手上的数。

令 s=\prod\limits_{i=1}^{x-1}a\times a_0，其实就是第 x 个大臣前面所有人左手的数之积。

当 x 大臣排在 x+1 大臣前时，这两个大臣对答案的贡献为

把第 x 与第 x+1 位大臣交换后的贡献：

如果 x+1 大臣排在 x 大臣前时更优，即

注意这里是严格小于。

而我们知道 \lfloor\frac{s\times a_{x+1}}{b_x}\rfloor\geq\lfloor\frac{s}{b_x}\rfloor，所以应当满足要求 \lfloor\frac{s\times a_x}{b_{x+1}}\rfloor>\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor（具体原因看本文末尾），因为这里是严格大于，所以 \frac{s\times a_x}{b_{x+1}}>\frac{s\times a_{x+1}}{b_x}，所以 a_x\times b_x>a_{x+1}\times b_{x+1}。那么按照每个大臣左右手的数之积排序就可以了。（如果当前转态是没有排序的，那么一定可以使用冒泡排序的思路将其变为排序好的，而每一次交换都会使答案更优，所以这样排序是正确的）

代码：因为我懒，所以没打高精

#include<bits/stdc++.h>
using namespace std;
#define int long long
pair<int,int>p[1005]/*大臣们*/,p1/*国王*/;
int n,ans,s;
signed main(){
    cin>>n>>p1.first>>p1.second;
    for(int i=1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
    }
    sort(p+1,p+n+1,[&](pair<int,int>a,pair<int,int>b){return a.first*a.second<b.first*b.second;});
    s=p1.first;
    for(int i=1;i<=n;i++){
        ans=max(s/p[i].second,ans);
        s*=p[i].first;
    }
    cout<<ans;
    return 0;
}

\lfloor\frac{s\times a_x}{b_{x+1}}\rfloor>\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor 的原因

若 \lfloor\frac{s\times a_x}{b_{x+1}}\rfloor\le\lfloor\frac{s}{b_x}\rfloor，那么 \max(\lfloor\frac{s}{b_{x+1}}\rfloor,\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor)<\lfloor\frac{s}{b_x}\rfloor，所以\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor<\lfloor\frac{s}{b_x}\rfloor（若 \max(a,b)<c，则 a<c 且 b<c），这与\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor\geq\lfloor\frac{s}{b_x}\rfloor 矛盾，所以\lfloor\frac{s\times a_x}{b_{x+1}}\rfloor>\lfloor\frac{s}{b_x}\rfloor，所以 \max(\lfloor\frac{s}{b_{x+1}}\rfloor,\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor)<\lfloor\frac{s\times a_x}{b_{x+1}}\rfloor，所以\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor<\lfloor\frac{s\times a_x}{b_{x+1}}\rfloor，即 \lfloor\frac{s\times a_x}{b_{x+1}}\rfloor>\lfloor\frac{s\times a_{x+1}}{b_x}\rfloor。