当前位置:网站首页>Codeforces - 1526C1&&C2 - Potions
Codeforces - 1526C1&&C2 - Potions
2022-07-06 09:28:00 【你好_Ä】
Codeforces - C1&&C2 - Potions
There are n potions in a line, with potion 1 on the far left and potion n on the far right. Each potion will increase your health by ai when drunk. ai can be negative, meaning that potion will decrease will health.
You start with 0 health and you will walk from left to right, from first potion to the last one. At each potion, you may choose to drink it or ignore it. You must ensure that your health is always non-negative.
What is the largest number of potions you can drink?
Input
The first line contains a single integer n (1≤n≤200000) — the number of potions.
The next line contains n integers a1, a2, … ,an (−109≤ai≤109) which represent the change in health after drinking that potion.
Output
Output a single integer, the maximum number of potions you can drink without your health becoming negative.
Example
input
6
4 -4 1 -3 1 -3
output
5
问题解析
这题是说有n瓶药,吃了之后会恢复a[i]点生命值或减少a[i]点生命值,你从左往右按顺序吃(也可以选择不吃),问你在生命值不为负的情况下能吃几瓶药。
因为c1和c2仅有数据大小的差异,我就直接按照c2来写,这题可以直接贪心写,把那些小的药水都忽略掉即可。
我们可以准备一个小根堆,从左往右将药剂插入小根堆中,当小根堆总和为负了,就把它最小的元素弹出,直到总和不为负为止,在此过程中维护一下吃下药水数的最大值即可。每次插入和弹出都是logn,所以总复杂度才nlogn。
AC代码
#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#define endl '\n'
#define int ll
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 2e5 + 50;
int n, m;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t;
int n;
cin >> n;
vector<int>v(n);
priority_queue<int,vector<int>,greater<int>>que;
int res = 0,ans=0;
for (int i = 0; i < n; i++)
{
cin >> v[i];
que.push(v[i]);
res += v[i];
while (res < 0)
{
res -= que.top();
que.pop();
}
ans = max(ans, (ll)que.size());
}
cout << ans << endl;
return 0;
}
边栏推荐
- 树莓派CSI/USB摄像头使用mjpg实现网页摄像头监控
- C basic grammar
- Share an example of running dash application in raspberry pie.
- C language is the watershed between low-level and high-level
- [exercise-8] (UVA 246) 10-20-30== simulation
- 969. Pancake sorting
- Radar equipment (greedy)
- Penetration test 2 --- XSS, CSRF, file upload, file inclusion, deserialization vulnerability
- 【练习-6】(PTA)分而治之
- HDU - 6024 building shops (girls' competition)
猜你喜欢
Penetration test (7) -- vulnerability scanning tool Nessus
Information security - Analysis of security orchestration automation and response (soar) technology
Pyside6 signal, slot
Advancedinstaller安装包自定义操作打开文件
渗透测试 ( 8 ) --- Burp Suite Pro 官方文档
QT实现圆角窗口
1013. Divide the array into three parts equal to and
第 300 场周赛 - 力扣(LeetCode)
Information security - threat detection - detailed design of NAT log access threat detection platform
Borg maze (bfs+ minimum spanning tree) (problem solving report)
随机推荐
Borg maze (bfs+ minimum spanning tree) (problem solving report)
Find 3-friendly Integers
Basic Q & A of introductory C language
[exercise -10] unread messages
Codeforces Round #801 (Div. 2)A~C
605. Planting flowers
Penetration test (4) -- detailed explanation of meterpreter command
Nodejs crawler
Some problems encountered in installing pytorch in windows11 CONDA
Common configuration files of SSM framework
分享一个在树莓派运行dash应用的实例。
渗透测试 ( 7 ) --- 漏洞扫描工具 Nessus
MySQL import database error [err] 1273 - unknown collation: 'utf8mb4_ 0900_ ai_ ci’
【练习-5】(Uva 839)Not so Mobile(天平)
Flask框架配置loguru日志库
Information security - threat detection - Flink broadcast stream broadcaststate dual stream merging application in filtering security logs
Interesting drink
409. Longest palindrome
807. Maintain the urban skyline
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞