【nowcoder 214272】减数游戏
游戏 nowcoder
2023-09-27 14:28:26 时间
减数游戏
题目链接: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;
}
相关文章
- 风暴英雄 http 302重定向 正在等待游戏模式下载完成
- 如何定位游戏发热问题
- 当随机不够随机:一个在线扑克游戏的教训
- 【BZOJ4554】[Tjoi2016&Heoi2016]游戏 二分图最大匹配
- 《HTML5游戏编程核心技术与实战》一2.2 图形API
- 《Java 2D游戏编程入门》—— 1.7 全屏显示模式中的主动渲染
- 《游戏编程模式》一7.9 层次状态机
- Flutter 游戏教程之使用 Flutter 和 Flame 重现著名的 T-Rex 游戏
- 华为快游戏调用登录接口失败,返回错误码 -1
- 【java养成】:main函数中String[] args的作用、商品入库案例、猜数字游戏、随机点名器
- 【bzoj4554】[Tjoi2016&Heoi2016]游戏 二分图最大匹配
- 【bzoj3105】[cqoi2013]新Nim游戏 高斯消元求线性基
- 【bzoj1775】[Usaco2009 Dec]Vidgame 电视游戏问题 dp