减数游戏

题目链接：nowcoder 214272

到主站看：https://blog.csdn.net/weixin_43346722/article/details/112730284

题目大意

有一个序列，你每次可以把两个数去掉，改成这两个数的乘积加 k。
然后问你变换到最后剩下的数最大可以是多少。

思路

这道题我们考虑贪心，可以看出肯定是选择最小的那两个乘。

那我们考虑用堆维护，但是你会发现乘到后面会有取模，然后就会导致堆里面最小的并不是真正最小的。

那怎么办呢？
那我们会发现，乘到最后，数已经很大了，把最小的两个乘起来，也会比之前最大的还要大。

那我们就考虑先用堆乘到这个情况（就先不取模），然后把身下的用一个队列维护，直接每次把对前面两个去掉变成它们的乘积加 。

代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define mo 1000000007

using namespace std;

queue <int> qq;
int n, k, ans, maxn;
ll x, y;
priority_queue <int, vector<int>, greater<int> > q; 

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        q.push(x);
        maxn = max(maxn, (int)x);
    }

    while (q.size() > 1) {
        x = q.top();
        q.pop();
        y = q.top();
        q.pop();

        if (x * y + k > maxn) {//最小的两个乘起来比原来最大的还要大了
            q.push(x);
            q.push(y);
            break;
        }

        q.push(x * y + k);
    }

    while (!q.empty()) {
        qq.push(q.top());
        q.pop();
    }

    while (qq.size() > 1) {
        x = qq.front();
        qq.pop();
        y = qq.front();
        qq.pop();

        qq.push(((ll)x * y + k) % mo);
    }

    printf("%d", qq.front()); 

    return 0;
}