B. Johnny and Grandmaster（贪心，双模法）

本文主要是介绍B. Johnny and Grandmaster（贪心，双模法），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

把 \(p^{k_1},p^{k_2},\cdots p^{k_n}\) 分成两个集合，使两个集合的总和的差的绝对值最小（是原数的差最小而不是取模后最小）。输出差的绝对值取模。

思路：

从大到小考虑每个数，如果 ans 为 0 则把当前数放入集合Ⅰ，即 ans 加上 \(p^i\)；

如果 ans 大于 0，说明集合Ⅰ比集合Ⅱ的和大（实际上一定恰好多出来 \(p^j\) ）。把数看成 p进制，后面的数一直放入集合Ⅱ直到 ans 等于0（说明用较小的数凑出了 \(p^j\)）。

ans 一直要取模，判断取模后的数是不是真的为0要用双模法！

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 5, M1 = 1e9 + 7, M2 = 1e9 + 3;
int n, p, k[N];
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = (ll)res * t % p;
        t = (ll)t * t % p;
        k >>= 1;
    }
    return res;
}

signed main()
{
    int T; cin >> T; while(T--)
    {
        scanf("%d%d", &n, &p);
        for(int i = 1; i <= n; i++) scanf("%d", &k[i]);

        sort(k + 1, k + 1 + n, greater<int>());

        int ans1 = 0, ans2 = 0;
        for(int i = 1; i <= n; i++)
        {
            if(ans1 || ans2) //不是0
                ans1 = (ans1 - qmi(p, k[i], M1) + M1) % M1,
                ans2 = (ans2 - qmi(p, k[i], M2) + M2) % M2;
            else //是0
                ans1 = (ans1 + qmi(p, k[i], M1)) % M1,
                ans2 = (ans2 + qmi(p, k[i], M2)) % M2;
        }

        printf("%d\n", ans1);
    }

    return 0;
}

这篇关于B. Johnny and Grandmaster（贪心，双模法）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！