算法刷题【洛谷P1080 & NOIP2012 提高组】国王游戏（附sort cmp函数使用警告）

2022-04-17

异想之旅：本人原创博客完全手敲，绝对非搬运，全网不可能有重复；本人无团队，仅为技术爱好者进行分享，所有内容不牵扯广告。本人所有文章仅在CSDN、掘金和个人博客（一定是异想之旅域名）发布，除此之外全部是盗文！

洛谷 P1080 国王游戏

题目描述

恰逢 $H$ 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

输入格式

第一行包含一个整数 $n$ ，表示大臣的人数。

第二行包含两个整数 $a$ 和 $b$ ，之间用一个空格隔开，分别表示国王左手和右手上的整数。

接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$ ，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

输入输出样例

In 1：

Out 1：

由于本题特殊情况较多，这里多给出2个样例（分别为洛谷评测样例 #6 和 #7）方便调试

In 3：

100 70 94 43 9 92 18 18 9 86 31 24 32 46 49 23 69 40 56 27 75 28 85 37 29 99 80 44 70 14 9 30 38 46 32 93 87 42 49 35 60 99 73 57 8 38 35 73 33 6 32 10 36 78 75 49 98 50 48 91 78 18 3 86 24 18 84 27 28 83 25 15 95 38 18 50 89 79 9 3 17 1 52 74 32 76 99 24 36 9 43 93 7 65 27 36 84 75 31 94 44 33 2 85 5 42 18 4 33 45 84 92 87 86 34 36 44 61 59 59 28 1 97 60 23 9 64 96 47 57 100 90 7 54 93 17 30 71 23 72 32 14 95 48 40 27 15 92 78 52 11 93 21 56 60 22 47 21 58 89 11 29 13 36 14 95 91 47 12 16 36 19 80 19 92 73 68 66 1 53 97 13 60 83 5 63 99 98 37 2 67 84 95 26 60 63 33 2 78 91 38 9 31

Out 3：

2166489661101032350678866897536628698296804147316726878162441737980268621335310233327258927458239967674879428851028800069063620140885606400000000000000000

In 4：

100 1 1 1 1 2 1 2 2 1 2 1 2 2 2 1 2 1 2 2 2 2 2 1 2 2 1 1 2 1 2 1 2 1 2 2 2 1 2 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 2 1 2 2 2 1 1 1 2 1 1 1 2 2 2 1 2 1 2 2 2 2 2 1 2 1 2 2 1 1 2 1 1 1 2 1 1 2 1 2 2 1 1 2 2 1 1 2 2 1 2 2 2 1 2 2 2 1 2 1 2 2 2 1 2 2 2 1 2 1 2 1 1 2 1 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 1 2 2 1 2 2 1 2 2 1 2 1 1 1 2 1 1 1 2 1 2 2 2 1 2 1 1 1 1 2 2 1 2 2 2 2 1 1 2 2 1 1 2 1 2 2 2 1 2 1 2 1 2 1 1 1 2

Out 4：

268435456

数据范围

对于 20%的数据，有 $1\leq n\leq 10, 0 < a,b < 8$ ；

对于 40%的数据，有 $1\leq n\leq20, 0 < a,b < 8$ ；

对于 60%的数据，有 $1\leq n\leq100$ ；

对于 60%的数据，保证答案不超过 $10^9$ ；

对于 100%的数据，有 $1 \leq n \leq1\times10^3, 0 < a,b < 1\times10^4$ 。

[video(video-Vu0VscZj-1644210108082)(type-csdn)(url-https://live.csdn.net/v/embed/185375)(image-https://live-file.csdnimg.cn/release/live/file/1644160551284.png?x-oss-process=image/resize,l_300)(title-算法刷题【洛谷P1080 & NOIP2012】国王游戏)]

对于100%的数据，看 Out 3 样例中输出的数字就知道了，高精度逃不过……本题中需要自己实现高精度乘法、高精除以int除法、高精度数字大小比较等。

不用高精度可以拿50分，~~我最开始没看题试过了~~

同时，高精度耦合，操作来操作去对C++字符串操作的熟悉程度也有很高要求。

另外就是大家都可以想到的，计算前一定要排序，且一定是一个贪心算法。接下来就来推理贪心的公式：

设当前有两个紧靠着的大臣 $i,i+1$ ，其中大臣 $i$ 左手数字为 $L_i$ ，右手数字为 $R_i$ ；同理大臣 $i+1$ 左手数字为 $L_{i+1}$ ，右手数字为 $R_{i+1}$ 。在 $0$ 到 $i$ 之间的大臣（包括皇帝）左手数字乘积为 $T$ 。
此时（交换前）大臣 $i$ 获得的钱为 $\frac{T}{R_i}$ ，大臣 $i+1$ 获得的钱为 $\frac{T \times L_i}{R_{(i+1)}}$
交换两人位置，交换后大臣 $i+1$ 获得的钱为 $\frac{T}{R_{(i+1)}}$ ，大臣 $i$ 获得的钱为 $\frac{T \times L_{(i+1)}}{R_i}$
由数据范围 $0 < a,b < 1\times10^4$ $0 < a, b < 1 \times 1 0^{4}$ 可知
- 交换前大臣 $i$ 的钱数 小于等于 交换后大臣 $i$ 的钱数，即 $\frac{T}{R_i} \leq \frac{T \times L_{(i+1)}}{R_i}$ 恒成立，进而若最大值出现于交换前，则最大值为交换前大臣 $i+1$ 的钱数，即 $max_1=\frac{T \times L_i}{R_{(i+1)}}$
- 交换前大臣 $i+1$ 的钱数 大于等于 交换后大臣 $i+1$ 的钱数，即 $\frac{T \times L_i}{R_{(i+1)}} ≥ \frac{T}{R_{(i+1)}}$ 恒成立，进而若最大值出现于交换后，则最大值为交换后大臣 $i$ 的钱数，即 $max_2=\frac{T \times L_{(i+1)}}{R_i}$
由上方两条结论可知，若交换前最大值更小，换句话说就是当前大臣 $i$ 和 $i+1$ 的排列顺序满足题目要求，则有 $max_1 \leq max_2$ ，即 $\frac{T \times L_i}{R_{(i+1)}} \leq \frac{T \times L_{(i+1)}}{R_i}$
对于上式，两边同除以 $T$ ，再同乘 $R_i R_{(i+1)}$ ，化简后得到 $L_iR_i \leq L_{(i+1)}R_{(i+1)}$ 。

证毕。

~~我敢说我比任何题解证得好~~

但是此处需要注意一件事！

就是题目中提到了的 sort cmp 函数使用警告——cmp函数的比较符必须是开区间！具体见下面这个例子

bool cmp(int a, int b) {
	// 错误
	// return a >= b;
	// 正确
	return a > b;
}

使用闭区间，否则Windows会莫名退出，Linux显示错误信息 Segmentation fault 外无更多提示。

如果想要研究原理，可以看看这两个文章（蒟蒻看不懂）：

剩下的高精度就很简单了。此处高精度此处优化下，全部使用函数封装好后，加一个参数接收存储答案的数组的地址，这样就不用太多全局变量造成混乱，也让主函数的代码简洁多了。

建议大家高精度还是自己再写一遍了，直接抄没啥进步，这玩意真的在赛场上遇到还是挺麻烦的，真的想考你的题 128_int 也是扛不住的啊。

AC代码：

#include <bits/stdc++.h>
using namespace std;

int n;
struct node {
    int a, b;
} a[100010];

bool cmp(node &x, node &y) {
    // 虽然证明时是小于等于即可，但是cmp千万不能用<=，上文说明了！
    return (x.a * x.b) < (y.a * y.b);
}

bool str_bigger(char x[], char y[]) {
    // 比较两个字符串类型的数字大小
    if (strlen(x) > strlen(y))
        return true;
    else if (strlen(x) < strlen(y))
        return false;
    else {
    	int len = strlen(x);
        for (int i = 0; i < len; i++)
            if (x[i] > y[i])
                return true;
            else if (x[i] < y[i])
                return false;
        return false;
    }
}

void to_string(int num, char *tmp) {
    // 将整数转换为字符串
    int cnt = 0;
    while (num) {
        tmp[cnt++] = num % 10 + '0';
        num /= 10;
    }
    tmp[cnt] = '\0';
    for (int i = 0; i < cnt / 2; i++) {
        swap(tmp[i], tmp[cnt - i - 1]);
    }
}

void mul(char xx[], char yy[], char *ans) {
    // 高精度乘法，ans为结果，xx为第一个数，yy为第二个数
    int lenx = strlen(xx), leny = strlen(yy);
    int x[10001], y[10001], z[10001];
    for (int i = 0; i < lenx; i++) x[lenx - i - 1] = xx[i] - '0';
    for (int i = 0; i < leny; i++) y[leny - i - 1] = yy[i] - '0';

    memset(z, 0, sizeof(z));
    for (int i = 0; i < lenx; i++) {
        for (int j = 0; j < leny; j++) {
            z[i + j] += x[i] * y[j];
            z[i + j + 1] += z[i + j] / 10;
            z[i + j] %= 10;
        }
    }
    int lenans = lenx + leny;
    while (z[lenans] == 0 && lenans) lenans--;

    for (int i = lenans; i >= 0; i--) ans[i] = z[lenans - i] + '0';
    ans[lenans + 1] = '\0';
}

void div(char a[], int b, char *ans) {
    // 高精度除法，ans为结果，a为被除数，b为除数
    int c[10001];
    memset(c, 0, sizeof(ans));
    int len = strlen(a);
    int k = 0;  // 每一位的余数
    for (int i = 0; i < len; i++) {
        c[i] = k * 10 + a[i] - '0';
        k = c[i] % b;
        c[i] /= b;
    }
    int i = 0;
    while (c[i] == 0 && i < len - 1) i++;
    for (int j = i; j < len; j++) ans[j - i] = c[j] + '0';
    ans[len - i] = '\0';
}

int main() {
    cin >> n >> a[0].a >> a[0].b;
    char t[100010];  // 每个大臣前面所有大臣左手上数字的积（包括国王）
    to_string(a[0].a, t);  // 将国王的左手上数字存入t
    char ans[100010];

    // 输入数据并排序
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b;
    }
    sort(a + 1, a + n + 1, cmp);

    // 开始遍历计算
    for (int i = 1; i <= n; i++) {
        // 计算当前大臣的钱数
        char tmp[100010];
        div(t, a[i].b, tmp);

        // 比较大小，决定是否存为ans
        if (str_bigger(tmp, ans)) {
            strcpy(ans, tmp);
        }

        // 将当前大臣左手的数字乘进t里面
        char tmp1[100010];
        to_string(a[i].a, tmp1);
        mul(t, tmp1, tmp);
        strcpy(t, tmp);
    }

    cout << ans << endl;

    return 0;
}

不得不说高精度速度还是挺快的，前几个点按毫秒算时间才个位数，和普通加法乘法几乎无差别。

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)