HackerEarth Vegetable Market problem solution

In this HackerEarth Vegetable Market problem solution, There are N stalls in a vegetable market that are selling vegetables. You have to buy an equal amount of vegetables from each stall. If a stall does not have enough vegetables to offer, then you have to buy all the vegetables available in that stall. If you are given the number of vegetables that every stall can offer, determine the minimum quantity that you need to buy from each stall such that you have at least K vegetables in total.

HackerEarth Vegetable Market problem solution.

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define si(x) scanf("%d", &x)
#define sc(x) scanf("%c", &x)
#define sl(x) scanf("%lld", &x)
#define pl(x) printf("%lldn", x)
#define pi(x) printf("%dn", x)
#define gu getchar_unlocked
#define pu putchar_unlocked
#define setbits __builtin_popcountll
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define speed ios::sync_with_stdio(false)

ll arr[100005];
ll leftarr[1000005], rightarr[1000005];
vector <ll> quan(1000005, 0);

int main(){
  int n, i;
  si(n);
  for(i = 1; i <= n; i++){
    sl(arr[i]);
    leftarr[arr[i]]++;
    rightarr[arr[i]]++;
  }
  for(i = 1; i <= 1000002; i++){
    leftarr[i] = leftarr[i - 1] + (i * leftarr[i]);
  }
  for(i = 1000002; i >= 0; i--){
    rightarr[i] += rightarr[i + 1];
  }
  for(i = 1; i <= 1000002; i++){
    quan[i] = leftarr[i - 1] + (rightarr[i] * i);
  }
  int q;
  si(q);
  while(q--){
    ll K;
    sl(K);
    vector <ll> :: iterator it;
    it = lower_bound(quan.begin(), quan.end(), K);
    if(it != quan.end()){
      int index = it - quan.begin();
      pi(index);
    }
    else{
      pi(-1);
    }
  }
}

HackerEarth Vegetable Market problem solution.

Leave a Reply