[NOIP2012 提高组] 国王游戏

news/2024/10/24 1:41:06

前言

题目传送门：https://www.luogu.com.cn/problem/P1080
依然是看题解会的，博主是飞舞。
找不到题解出处了，只记得在csdn上看的，果咩那塞原博主。

题目大意

有\(1\)个国王和\(n\)个大臣，每个人左手和右手都写了一个数字。
国王站在队首，\(n\)个大臣排在后面。
每个大臣能获得的金币数为前面所有人左手数字的乘积除以本人右手数字（向下取整）。
问能获得最多金币的大臣的金币数最小为多少。

思路

题目分析

由分析可知，对于第\(i\)个大臣来说，前面的\(i-1\)个大臣的顺序无论怎么变化，只要这\(i-1\)个人是确定的，都不影响第\(i\)个大臣的金币数。

所以在分析时我们先假定前\(i-1\)个大臣的左手积是固定的，设为\(S\)
讨论第\(i\)和\(i+1\)大臣的先后顺序
设\(a_i\)为此时第\(i\)个大臣的左手的数，\(b_i\)为右手
那么第\(i\)个大臣的金币为\(S/b_i\)
第\(i+1\)个大臣的金币为\(S \cdot a_i/b_{i+1}\)

若两人交换位置
则第\(i\)个位置的金币为\(S/b_{i+1}\)
\(i+1\)个位置为\(S\cdot a_{i+1}/b_i\)
若换位后第i+1位置的金币和原来比不减少，即

\[S \cdot a_i/b_{i+1} \leq S\cdot a_{i+1}/b_i \]

化简得

\[a_i \cdot b_i \leq a_{i+1}\cdot b_{i+1} \]

接下来证明在这个公式约束下，最后一个大臣的金币是最大的
即证明交换位置后第\(i\)位的金币不大于第\(i+1\)位
即证明

\[S/b_{i+1} \leq S \cdot a_{i+1}/b_i \]

化简得

\[b_i \leq a_{i+1} \cdot b_{i+1} \]

由数据范围可知：\(a_i \geq 1\)，所以该式显然成立，命题得证

注意事项

由数据范围\(1≤𝑛≤1,000,0<𝑎,𝑏<10000\)可知
最大的积可能为\(10000^{1000}=10^{4\times1000}=10^{4000}\)
所以明显要用到高精，具体到本题，就是高精除和高精乘

代码

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3f
#define ll long long
using namespace std;ll n, a, b, cnt = 1; //cnt记录高精数的位数
ll x[4005] = {1}, y[4005]; //高精乘基础值为1struct info {ll x;ll y;bool operator<(const info &o)const {return x * y < o.x * o.y;}
} e[1005];void mtp(ll u);
void div(ll u);
void print();
void solve();void mtp(ll u) { //高精乘ll temp = 0;for (ll i = 0; i < cnt; ++i) {x[i] *= u;}for (ll i = 0; i < cnt; ++i) {temp += x[i];x[i] = temp % 10;temp /= 10;}while (temp != 0) {x[cnt] = temp % 10;cnt++;temp /= 10;}
}void div(ll u) { //高精除ll temp = 0;for (ll i = cnt - 1; i >= 0; i--) {temp = temp * 10 + x[i];y[i] = temp / u;temp %= u;}
}void print() {ll temp = cnt;if (n == 1) { //特判只有一个大臣的情况cout << e[0].x / e[1].y << '\n';} else {while (y[temp] == 0) { //去掉前置0temp--;if (temp == -1) { //保证每个大臣至少会得到一个金币？cout<<1<<'\n'; //“所有的大臣都会获得国王奖赏的若干金币”return ; //感觉题目应该说的更明白一点}}for (ll i = temp; i >= 0; i--) { //打印高精数cout << y[i];}}
}void solve() {cin >> n;for (ll i = 0; i <= n; i++) {cin >> e[i].x >> e[i].y; //读入国王和大臣}sort(e + 1, e + n + 1); //仅对大臣排序for (ll i = 0; i < n; i++) {mtp(e[i].x); //对前面的国王和n-1个大臣累乘}div(e[n].y); //已证明得最后的大臣的金币最大，所以只用看最后一个大臣的金币print();
}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);ll t = 1;
//	cin>>t;while (t--) {solve();}return 0;
}