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

ops/2024/10/30 10:58:13/

题目链接

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.ppmy.cn/ops/129559.html

相关文章

【机器学习】Softmax 函数

Softmax 是机器学习中常用的函数&#xff0c;广泛用于多分类问题的输出层。它可以将一组实数转换为一个概率分布&#xff0c;使得结果满足“非负”和“总和为1”的要求。在分类问题中&#xff0c;Softmax 让模型预测的每个类别概率都易于解释。本文将详细讲解 Softmax 的原理、…

详解:单例模式中的饿汉式和懒汉式

单例模式是一种常用的设计模式&#xff0c;其目的是确保一个类只有一个实例&#xff08;对象&#xff09;&#xff0c;并提供一个全局访问点。单例模式有两种常见的实现方式&#xff1a;饿汉式和懒汉式。 一、饿汉式 饿汉式在类加载时就完成了实例化。因为类加载是线程安全的&…

设计模式06-结构型模式1(适配器/桥接/组合模式/Java)

#1024程序员节&#xff5c;征文# 4.1 适配器模式 结构型模式&#xff08;Structural Pattern&#xff09;的主要目的就是将不同的类和对象组合在一起&#xff0c;形成更大或者更复杂的结构体。结构性模式的分类&#xff1a; ​ 类结构型模式关心类的组合&#xff0c;由多个类…

C语言中的位操作

第一章 变量某位赋值与连续赋值 寄存器 | 值 //例如&#xff1a;a 1000 0011b a | (1<<2) //a 1000 0111 b 单独赋值 a | (3<<2*2) // 1011 0011b 连续赋值 第二章 变量某位清零与连续清零 寄存器 & ~&#xff08;&#xff09; 值 //例子&#xff1a;a …

MATLAB车道检测与跟踪

读了车道检测这个论文&#xff0c;我理解了利用matlab对车道识别算法进行仿真研究&#xff0c;从仿真的结果中提出具有一定实时性鲁棒性的识别方法。车道检测是智能车辆发展的智能因素。近年来对这项目的研究都是针对特定的环境和道路状况给出了不同的解决方案。近年来,自主驾驶…

NVR小程序接入平台/设备EasyNVR多个NVR同时管理视频监控新选择

在数字化转型的浪潮中&#xff0c;视频监控作为安防领域的核心组成部分&#xff0c;正经历着前所未有的技术革新。随着技术的不断进步和应用场景的不断拓展&#xff0c;视频监控系统的兼容性、稳定性以及安全性成为了用户关注的焦点。NVR小程序接入平台/设备EasyNVR&#xff0c…

【本科毕业设计】基于单片机的智能家居防火防盗报警系统

基于单片机的智能家居防火防盗报警系统 源码下载摘要Abstract第1章 绪论1.1课题的背景1.2 研究的目的和意义 第2章 系统总体方案设计2.1 设计要求2.2 方案选择和论证2.2.1 单片机的选择2.2.2 显示方案的选择 第3章 系统硬件设计3.1 整体方案设计3.1.1 系统概述3.1.2 系统框图 3…

核心HTML5/CSS3基础面试题

HTML5/CSS3 高频经典面试题 汇总了 2023 年各互联网大厂以及中小型创业公司基础阶段的最新高频面试题 HTML/HTML5 标签 Interview questions 1、说说你对 HTML 语义化的理解 ?HTML5 新增了哪些语义化标签 ?(字节、百度,阿里,腾讯、京东,小米) 2、DOCTYPE 是干嘛的,…