減數游戲
題目鏈接：nowcoder 214272
到牛客看：
——>點我跳轉<——
題目大意
有一個序列，你每次可以把兩個數去掉，改成這兩個數的乘積加 k，
然后問你變換到最后剩下的數最大可以是多少，
思路
這道題我們考慮貪心，可以看出肯定是選擇最小的那兩個乘，
那我們考慮用堆維護，但是你會發現乘到后面會有取模，然后就會導致堆里面最小的并不是真正最小的，
那怎么辦呢？
那我們會發現，乘到最后，數已經很大了，把最小的兩個乘起來，也會比之前最大的還要大，
那我們就考慮先用堆乘到這個情況（就先不取模），然后把身下的用一個佇列維護，直接每次把對前面兩個去掉變成它們的乘積加 k k 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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/250769.html
標籤：其他