Potions (Easy Version)（优先队列，反悔贪心）

科技前沿 • 2025-03-13 16:11 • 阅读 40

大家好，我是讯享网，很高兴认识大家。

Potions (Easy Version)（优先队列，反悔贪心）

This is the easy version of the problem. The only difference is that in this version n≤2000. You can make hacks only if both versions of the problem are solved.

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≤2000) — 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

Note
For the sample, you can drink 5 potions by taking potions 1, 3, 4, 5 and 6. It is not possible to drink all 6 potions because your health will go negative at some point

题意： 给个n，有n瓶药剂，可喝可不喝，初始生命值为0，喝下去，血量就+x（x可为负），保证每次喝完血量不为负，问最多能喝几瓶

思路： 遍历一遍，把负数的绝对值用优先队列（自动排序，从大到小）存起来，遇见就加，直到当前血量为负，就加队首，然后让队首出队，当前血量为负，最不应该喝的就是绝对值最大的负数，此时就反悔，不喝这瓶药就行了

AC代码：

#include<stdio.h> #include<string.h> #include<queue> #include<algorithm> using namespace std; int a[2100]; int main() { 
    long long n,i,j,k,x; priority_queue<int>q;//优先队列有自动排序的功能（从大到小） scanf("%lld",&n); long long sum=0; k=0;//记录个数 for(i=0; i<n; i++) { 
    scanf("%lld",&x); sum+=x;//遇见就加 k++; if(x<0)//负数的绝对值存优先队列 q.push(-x); if(sum<0)//血量为负，就反悔 { 
    j=q.top();//printf("%d+++\n",j); sum+=j; q.pop(); k--; } }// printf("%d----\n",sum); printf("%lld\n",k); return 0; }

讯享网

Potions (Easy Version)（优先队列，反悔贪心）

Potions (Easy Version)（优先队列，反悔贪心）

相关推荐