2012S_2：国王游戏
洛谷：P1080
OJ：P5967
题目分析：
本题需要高精乘法和除法：
当 N 较大时，左手数字的乘积可能会非常大。即使单个左手数不大，经过多次乘法后，乘积会快速增长，导致无法使用标准的 int 或 long long 类型来存储这些中间结果。
我们考虑两个大臣p1,p2，它们站在国王p0的身后，则这两个大臣有两种排列方案：
方案一： p1站在p2的前面
| person | left | right |
|---|---|---|
| p0 | a0 | b0 |
| p1 | a1 | b1 |
| p2 | a2 | b2 |
方案二：p1站在p2的后面
| person | left | right |
|---|---|---|
| p0 | a0 | b0 |
| p2 | a2 | b2 |
| p1 | a1 | b1 |
对于第一种情况，答案 ans1=max(\(\frac{a_{0}}{b_{1}}\), \(\frac{a_{0}a_{1}}{b_{2}}\))
对于第二种情况，答案 ans2=max(\(\frac{a_{0}}{b_{2}}\), \(\frac{a_{0}a_{2}}{b_{1}}\))
显然， \(\frac{a_{0}a_{1}}{b_{2}}\)>\(\frac{a_{0}}{b_{2}}\) , \(\frac{a_{0}a_{2}}{b_{1}}\)>\(\frac{a_{0}}{b_{1}}\)
若ans1<ans2, \(\frac{a_{0}a_{2}}{b_{1}}\)> \(\frac{a_{0}a_{1}}{b_{2}}\)
即： \(\frac{a_{2}}{b_{1}}\)>\(\frac{a_{1}}{b_{2}}\) , a1b1<a2b2
若 a1b1<a2b2 p1就应该排在p2前更优，也就是最大值更小。
如果p0和p1之间还有若干大臣，也不影响p1和p2之间的位置关系做带来的结果。
因此，我们得出结论：如果aibi<ajbj，那么应当让i排在j的前方，即按照ai*bi的大小从小到大排序。
代码一： 手写快排+高精度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 | #include<cstdio> #include<cstring> #include<algorithm> #include <iostream> using namespace std; int N; // 大臣人数 int a[1005], b[1005], ka, kb; // a存左手数，b存右手数，ka和kb是国王的左右手数 int ans[20000], t[20000], lena, lent, tt[20000], t2[20000], len; // ans存储最终答案，t和tt等是用于计算过程的临时数组 // 快速排序函数，用于按照a[i]*b[i]的值排序大臣 void qst_ab(int l, int r) { int i = l, j = r, ma = a[(i+j)>>1], mb = b[(i+j)>>1]; // 选取中间值作为基准 while (i <= j) { // 找到左边第一个不符合条件的a[i]和b[i]（a[i]*b[i] >= ma*mb） while (a[i] * b[i] < ma * mb) i++; // 找到右边第一个不符合条件的a[j]和b[j]（a[j]*b[j] <= ma*mb） while (a[j] * b[j] > ma * mb) j--; // 交换不符合条件的两个大臣 if (i <= j) { swap(a[i], a[j]); swap(b[i], b[j]); i++; j--; } } // 递归地对左右两部分继续排序 if (l < j) qst_ab(l, j); if (i < r) qst_ab(i, r); } // 初始化函数，读取输入 void init() { cin>>N>>a[0]>>b[0]; // 读取国王的左手和右手数 for (int i = 1; i <= N; i++) // 读取每个大臣的左手和右手数 cin>>a[i]>>b[i]; } // 计算每个大臣获得的金币 void _get_t(int Left, int Right) { // 将当前乘积t与大臣左手数字Left相乘，并存入tt数组 for (int i = 1; i <= lent; i++) { tt[i] += t[i] * Left; tt[i+1] += tt[i] / 10; // 处理进位 tt[i] %= 10; } lent++; while (tt[lent] >= 10) { // 处理多位进位 tt[lent+1] = tt[lent] / 10; tt[lent] %= 10; lent++; } while (lent > 1 && tt[lent] == 0) lent--; // 去掉前导零 len = lent; // 更新长度 memcpy(t, tt, sizeof(tt)); // 将tt的内容复制回t memset(tt, 0, sizeof(tt)); // 清空tt // 将t逆序存入t2（处理右手数字的除法） for (int i = 1, j = len; i <= len; i++, j--) t2[i] = t[j]; int x = 0, y = 0; // 逐位进行除法运算，将t2中的大数字依次除以Right，存入tt for (int i = 1; i <= len; i++) { y = x * 10 + t2[i]; tt[i] = y / Right; x = y % Right; } x = 1; // 去掉tt中的前导零 while (x < len && tt[x] == 0) x++; memset(t2, 0, sizeof(t2)); // 清空t2 // 将tt复制到t2中并调整位置 for (int i = 1, j = x; j <= len; i++, j++) t2[i] = tt[j]; memcpy(tt, t2, sizeof(t2)); // 将t2的结果复制回tt len = len + 1 - x; // 更新最终结果长度 } // 比较函数，用于比较当前的金币数量与最优答案 bool _cmp() { if (len > lena) return true; // 如果当前长度比最优答案长，表示当前值更大 if (len < lena) return false; // 如果当前长度比最优答案短，表示当前值更小 for (int i = 1; i <= len; i++) { if (ans[i] < tt[i]) return true; // 如果当前值更大，返回true if (ans[i] > tt[i]) return false; // 如果当前值更小，返回false } return false; } // 核心求解函数 void _solve() { qst_ab(1, N); // 根据a[i]*b[i]排序大臣 t[1] = 1; lent = 1; // 初始化乘积t为1 // 遍历每个大臣，计算每个大臣的奖赏，并与当前最优答案进行比较 for (int i = 1; i <= N; i++) { memset(tt, 0, sizeof(tt)); // 清空tt len = 0; _get_t(a[i-1], b[i]); // 计算当前大臣的奖赏 if (_cmp()) { // 如果当前奖赏更小，则更新最优答案 memcpy(ans, tt, sizeof(tt)); lena = len; } } // 输出最终最优答案（即最小的最大奖赏） for (int i = 1; i <= lena; i++)cout<<ans[i]; // printf("\n"); } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); init(); // 读取输入 _solve(); // 求解并输出结果 return 0; } |
代码实现二：用sort+pair+高精度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include <iostream> #include <string.h> #include <vector> #include <algorithm> using namespace std; int N; // 大臣人数 pair<int, int> king; // 国王的左右手数 vector<pair<int, int>> ministers; // 存储每个大臣的左右手数 int ans[20000], t[20000], lena, lent, tt[20000], t2[20000], len; // 高精度计算用的数组 // 比较函数，用于排序大臣的乘积 bool compareMinisters(const pair<int, int>& a, const pair<int, int>& b) { return a.first * a.second < b.first * b.second; } // 初始化函数，读取输入 void initialize() { cin >> N >> king.first >> king.second; // 读取国王的左右手数 ministers.resize(N); // 调整大臣数据的大小 for (int i = 0; i < N; i++) { cin >> ministers[i].first >> ministers[i].second; // 每个大臣的左右手数 } } // 计算当前大臣的奖赏 void calculateReward(int leftProduct, int currentRight) { for (int i = 1; i <= lent; i++) { tt[i] += t[i] * leftProduct; // 更新乘积 tt[i + 1] += tt[i] / 10; // 处理进位 tt[i] %= 10; } lent++; while (tt[lent] >= 10) { tt[lent + 1] = tt[lent] / 10; tt[lent] %= 10; lent++; } while (lent > 1 && tt[lent] == 0) lent--; // 去除前导零 len = lent; memcpy(t, tt, sizeof(tt)); // 复制结果 memset(tt, 0, sizeof(tt)); for (int i = 1, j = len; i <= len; i++, j--) t2[i] = t[j]; // 逆序 int carry = 0, remainder = 0; for (int i = 1; i <= len; i++) { remainder = carry * 10 + t2[i]; tt[i] = remainder / currentRight; carry = remainder % currentRight; } int startIndex = 1; while (startIndex < len && tt[startIndex] == 0) startIndex++; memset(t2, 0, sizeof(t2)); for (int i = 1, j = startIndex; j <= len; i++, j++) t2[i] = tt[j]; memcpy(tt, t2, sizeof(t2)); len = len + 1 - startIndex; } // 比较当前计算结果是否更优 bool isBetter() { if (len > lena) return true; if (len < lena) return false; for (int i = 1; i <= len; i++) { if (ans[i] < tt[i]) return true; if (ans[i] > tt[i]) return false; } return false; } // 核心求解函数 void solve() { // 使用 std::sort 对大臣按乘积排序 sort(ministers.begin(), ministers.end(), compareMinisters); t[1] = 1; lent = 1; // 初始化乘积为1 for (int i = 0; i < N; i++) { memset(tt, 0, sizeof(tt)); // 清空临时数组 len = 0; int leftProduct = (i == 0) ? king.first : ministers[i - 1].first; int currentRight = ministers[i].second; calculateReward(leftProduct, currentRight); // 计算当前大臣的奖赏 if (isBetter()) { // 如果当前结果更优，则更新 memcpy(ans, tt, sizeof(tt)); lena = len; } } // 输出最终答案 for (int i = 1; i <= lena; i++) { cout << ans[i]; } cout << endl; } int main() { freopen("game.in","r",stdin); freopen("game.out","w",stdout); initialize(); // 读取输入 solve(); // 求解并输出结果 return 0; } |