Sinux's blog

By Sinux, history, 3 months ago, In English

I am struggling on solving the problem 1873E problem div4. I wrote the solution but few test cases are wrong and I can't find the flaw in my code. Plz Help!!!

#include <algorithm>
#include <iostream> 
#include <vector> 
using namespace std;
#define ll long long
int main() {
    ll t;
    cin >> t;
    while (t--) {
        ll n, x;
        cin >> n >> x;
        vector<ll> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a.begin(), a.end());
        ll left = 0, right = a[n - 1];
        ll height = 0;
        while (left <= right) {
            ll mid = (left + right) / 2;
            ll sum = 0;
            for (int i = 0; i < n; i++) {
                if (mid > a[i]) {
                    sum += mid - a[i];
                }
            }
            if (sum <= x) {
                height = mid;
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        cout << height << '\n'; 
    }

    return 0;
}

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I recommend you to skip this, it's a technique called binary search, which isn't advanced in any means but it's hard for your level, really hard, focus on other things