Блог пользователя tatya_bichu

Автор tatya_bichu, история, 3 года назад, По-английски

Guys, I wanted some help regarding a binary search problem given in the end of this video

Problem

I found this video very helpful! but still not able to solve the challenge posted in the video. I know it is a binary search problem so that we minimize the height of stacks so it must be a finding minimum value in curve, but how do we know that there is one minimum value in it?

Thank You.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

For finding min. cost , we need to find optimal height where there will be minima.

Now , there is a little twist because one can move the blocks also.

Check out my code for detailed explanation:

Approach: Binary Search

int A,R,M;
vector<int> height;
int getCost(int mid)
{
    int adds = 0; //number of blocks to be added
    int removes = 0; //number of blocks to be removed

    for(int i=0;i<n;i++)
    {
        if(height[i] > mid) removes += (abs(height[i]-mid));
        else if(height[i] < mid) adds += (abs(height[i]-mid));
    }

    //This is the cost where we have done only adds or only removes
    int cost = (adds > removes)?(adds-removes)*A:(removes-adds)*R;

    //Tricky part is that if (adds = removes) ,then we have to decide whether we need to move block or add/delete.
    cost += min(adds,removes)*min(A+R,M);

    return cost;
}

void solve()
{
    cin >> n;
    cin >> A >> R >> M;
    height.resize(n);
    for(int i=0;i<n;i++) cin>>height[i];

    int lo = 0,hi = *max_element(height.begin(),height.end());
    int tmp=hi;
    int ans ,ht;
    while(lo<=hi)
    {
        int mid = lo +(hi-lo)/2;
        int left = 0,right=0;

        //left and right or just checking whether left/right slope decreasing or not (-1 means dec.)
        if(mid>0 && getCost(mid-1) >= getCost(mid)) left = -1;
        if(mid<tmp && getCost(mid+1) >= getCost(mid)) right=-1;

        //If both slops are decreasing , we got minima!
        if(right == -1 && left==-1)
        {
            ans = getCost(mid);
            ht = mid;
            break;
        }

        //Else reducing search space
        if(right==-1) hi = mid;
        else if(left==-1) lo = mid;
    }

    //Cost as well as req. height
    cout << ans <<" " << ht<< endl;

}
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    chirag2505 Thanks brother, I understood most of the parts. Great work!, You are finding the minimum value in the curve as described in video, but how do we know that there will be one minimum value and why the curve should have ever increasing values on both side of minimum value? Also there can be multiple minima right?

    In that case the while loop will go forever, right?