当前位置:网站首页>Codeforces - 1526C1&&C2 - Potions
Codeforces - 1526C1&&C2 - Potions
2022-07-06 16:14:00 【Hello_ Ä】
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
Problem analysis
This question means yes n Bottle medicine , You will recover after eating a[i] Hit points or reduce a[i] Point health , You eat from left to right ( You can also choose not to eat ), Ask how many bottles of medicine you can take when your health value is not negative .
because c1 and c2 Only data size differences , I'll just follow c2 To write , This question can be directly written greedily , Just ignore those small potions .
We can prepare a small root pile , Insert the potion into the small root pile from left to right , When the sum of small root piles is negative , Just pop up the smallest element , Until the sum is not negative , In this process, maintain the maximum amount of water taken . Every insert and eject is logn, So the total complexity is nlogn.
AC Code
#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;
}
边栏推荐
- Advancedinstaller安装包自定义操作打开文件
- D - function (HDU - 6546) girls' competition
- Is the sanic asynchronous framework really so strong? Find truth in practice
- pytorch提取骨架(可微)
- 409. Longest palindrome
- 第 300 场周赛 - 力扣(LeetCode)
- Write web games in C language
- 生成随机密码/验证码
- [exercise-2] (UVA 712) s-trees
- Pyside6 signal, slot
猜你喜欢
C language is the watershed between low-level and high-level
Flask框架配置loguru日志庫
1013. Divide the array into three parts equal to and
[exercise-4] (UVA 11988) broken keyboard = = (linked list)
2027. Minimum number of operations to convert strings
Flask框架配置loguru日志库
QT实现窗口渐变消失QPropertyAnimation+进度条
力扣:第81场双周赛
921. Minimum additions to make parentheses valid
渗透测试 2 --- XSS、CSRF、文件上传、文件包含、反序列化漏洞
随机推荐
Nodejs crawler
Penetration test (3) -- Metasploit framework (MSF)
875. 爱吃香蕉的珂珂 - 力扣(LeetCode)
useEffect,函数组件挂载和卸载时触发
Codeforces Round #803 (Div. 2)A~C
2027. Minimum number of operations to convert strings
双向链表—全部操作
Alice and Bob (2021 Niuke summer multi school training camp 1)
Share an example of running dash application in raspberry pie.
Read and save zarr files
Basic Q & A of introductory C language
[teacher Gao UML software modeling foundation] collection of exercises and answers for level 20 cloud class
b站 實時彈幕和曆史彈幕 Protobuf 格式解析
Suffix expression (greed + thinking)
Information security - threat detection - detailed design of NAT log access threat detection platform
1005. Maximized array sum after K negations
QT实现圆角窗口
Flag framework configures loguru logstore
1903. Maximum odd number in string
Luogu P1102 A-B number pair (dichotomy, map, double pointer)