当前位置: 首页 > article >正文

Codeforces Round 946 (Div. 3) G. Money Buys Less Happiness Now(反悔贪心)

题目链接

Codeforces Round 946 (Div. 3) G. Money Buys Less Happiness Now

思路

我们维护当前拥有的钱 s u m sum sum和一个大根堆,大根堆记录用了哪些 c i c_{i} ci

我们先尝试获得当前月的幸福, s u m = s u m − c i sum = sum - c_{i} sum=sumci,并将 c i c_{i} ci扔到大根堆里。如果当前的 s u m < 0 sum < 0 sum<0,则需要进行反悔操作。从大根堆里面取出最大的 c k c_{k} ck,令 s u m = s u m + c k sum = sum + c_{k} sum=sum+ck即可。

在每个月的月末,我们让 s u m = s u m + x sum = sum + x sum=sum+x

最终的答案即为大根堆中 c i c_{i} ci的数量。

时间复杂度: O ( m l o g m ) O(mlogm) O(mlogm)

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int m, x;
int c[N];
void solve()
{
	cin >> m >> x;
	for (int i = 1; i <= m; i++)
	{
		cin >> c[i];
	}
	priority_queue<int, vector<int>, less<int>>q;
	int sum = x;
	for (int i = 2; i <= m; i++)
	{
		sum -= c[i];
		q.push(c[i]);
		if (sum < 0)
		{
			sum += q.top();
			q.pop();
		}
		sum += x;
	}
	cout << q.size() << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int test = 1;
	cin >> test;
	for (int i = 1; i <= test; i++)
	{
		solve();
	}
	return 0;
}

http://www.kler.cn/a/371243.html

相关文章:

  • 批量剪辑视频软件源码搭建全解析,支持OEM
  • 【C语言】预处理(预编译)详解(下)(C语言最终篇)
  • 重学SpringBoot3-怎样优雅停机
  • 前端自学资料(笔记八股)分享—CSS(4)
  • 基于神经网络的农业病虫害损失预测
  • 鸿蒙开发 五十一 Command Line Tools 之ohpm
  • Kafka的羊群效应
  • 基于微信小程序的音乐播放器系统
  • 〈壮志凌云:独行侠〉中的超高音速战机
  • vue3+ant design vue实现表格数据‘是‘‘否‘展示
  • 算法练习:LCR 179. 查找总价格为目标值的两个商品
  • mysql上课总结(1)(mysql中的常见的存储引擎)(面试)
  • Python Transformer 模型的基本原理:BERT 和 GPT 以及它们在情感分析中的应用
  • 【测试平台】打包 子节点ios环境配置
  • 一道巧妙的卡特兰数建模
  • 【Postfix】Docker Postfix中继服务的实践与优化
  • SpringBoot技术在商场应急管理中的创新应用
  • Python | Leetcode Python题解之第519题随机翻转矩阵
  • 四、Prompt工程——简单应用
  • vscode和pycharm在当前工作目录的不同|python获取当前文件目录和当前工作目录
  • js 获取当前时间与前一个月时间
  • 015:地理信息系统开发平台ArcGIS Engine10.2与ArcGIS SDK for the Microsoft .NET Framework安装教程
  • 【JavaEE初阶】网络原理—关于TCP协议值滑动窗口与流量控制,进来看看吧!!!
  • 2024年1024程序人生总结
  • Linux基础—基础命令及相关知识5(ubuntu网络配置)
  • 【C语言】预处理(预编译)详解(下)(C语言最终篇)