Help In Potions(HARD) Codeforces Round #723

help
,
1

Please Help Me In Potion(Hard)
Please Explain Full Solution Or Just Tell Which Algorithm To Apply
Question Link: Problem - C2 - Codeforces
My Approach: :exploding_head:

1 Like
2

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
3

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
4

Thanks @cubefreak777, @pie_3

1 Like
5 
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
6

@cubefreak777 Yes I Will, Could You PLEASE Share Any Article Or Some Site URL On HEAPS

2 Likes
7

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
8

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

2 Likes