EKO binary search : wrong answer when submit it

[darshil_812]

#include
#include <bits/stdc++.h>
using namespace std;

bool isPossible(long long tree[],int size, long long m, long long mid)
{
long long wood = 0;
for (int i = 0; i < size; i++)
{
if (tree[i] >= mid)
{
wood += (tree[i] - mid);

    }
}
if(wood >= m){
    return 1;
}
return 0;

}

int main()
{

int N;
long long M;
cin >> N;
cin >> M;
long long tree[N];

for (int i = 0; i < N; i++)
{
    cin >> tree[i];
}

long long s = 0, maxi = -1;
long long ans = -1;

for (int i = 0; i < N; i++)
{
    maxi = max(maxi, tree[i]);
}

long long e = maxi;
long long mid = s + (e - s)/2;

while (s <= e)
{
    if (isPossible(tree, N, M, mid))
    {
        ans = mid;
        s = mid + 1;
    }
    else
    {
        e = mid - 1;
    }
    mid = s + (e - s) / 2;
}
cout << "Answer : " << ans;
return 0;

}

[simes]

s = mid + 1;

I’ve not tested it, but I suspect this line. You know it’s possible to get the required amount of wood with a cut at mid, but it may not be possible to get the required amount of wood with a cut at mid + 1. I think you need to remove the + 1, and consider what to do if s is already the same value as mid.

[vella_assh0le]

HOW CAN I SUBMIT THIS SOLUTION WITH STDIN INPUT TEST CASES??? PLEASE HELP

/* Online C++ Compiler and Editor */
#include
#include

using namespace std;

bool isPossible(vector &heights, int mid, int wood) {
int totalWood = 0;
for(int i = 0; i < heights.size(); i++) {
if(heights[i] > mid) {
totalWood = totalWood + (heights[i] - mid);
}
if(totalWood > wood) {
return false;
}
}
return true;
}

int maximumHeightOfSawblade(vector &heights, int wood) {
int ans = -1;
int start = 0;
int maxi = -1;
for(int i = 0; i < heights.size(); i++) {
maxi = max(maxi, heights[i]);
}
int end = maxi;
int mid = start + (end - start)/2;
while(start<=end) {
if(isPossible(heights, mid, wood)) {
ans = mid;
end = mid - 1;
} else {
start = mid + 1;
}
mid = start + (end - start)/2;
}

return ans;

}

int main()
{
vector vect = {4, 42, 40, 26, 46};
int wood = 20;

int result = maximumHeightOfSawblade(vect, wood);
cout << result;
return 0;

}

[simes]

I don’t normally respond to comments that hijack another’s thread, but did you read the previous answer?