Please Help Me In Potion(Hard)

Please Explain Full Solution Or Just Tell Which Algorithm To Apply

Question Link: Problem - C2 - Codeforces

My Approach:

1 Like

Learn about heaps, I think that’s the easiest way to approach this problem.

## CODE

```
#include "bits/stdc++.h"
using namespace std ;
int main(){
long long n,s=0,ans=0;cin >> n ;
vector<int>a(n) ;
for(int &x:a)
cin >> x ;
priority_queue<int>pq ;
for(int i=0;i<n;i++){
s+=a[i],ans++ ;
pq.push(-a[i]) ;
if(s<0)
s+=pq.top(),pq.pop(),--ans ;
}
cout << ans ;
}
```

2 Likes

Use greedy

Run a loop

Keep a variable which stores sum and keep adding no.s to it.

Store negative no.s in a set. Whenever sum gets less than 0 add greatest absolute value from set.

1 Like

```
package com.codeforces;
import java.util.Arrays;
import java.util.Scanner;
public class PotionsEasy {
public static void main(String[] args){
Scanner scin = new Scanner(System.in);
int t = scin.nextInt();
int[] a = new int[t];
for (int i = 0; i < t; i++) {
a[i] = scin.nextInt();
}
Arrays.sort(a);
int current_count = 0;
int count = 0;
for (int i = a.length - 1; i >= 0; i--) {
current_count+=a[i];
if (current_count<0){
current_count+=Math.abs(a[i]);
}
else {
count++;
}
}
System.out.println(count);
}
}
```

I think you are saying this

1 Like

By heaps, I meant to say that you should at least be able to use the built-in PriorityQueues, like what are its properties, when to use it, other methods of PriorityQueue, etc… , though if you want to learn the actual working of priority queues(heaps) then you can check this

1 Like

Thanks @cubefreak777, Yes I Want To Learn Actual Working, The Tutorial You shared Is very Nice

2 Likes