3
\$\begingroup\$

I'm trying to solve the following problem:

As you know Bob likes to destroy the buildings. There are N buildings in a city, ith building has ai floors. Bob can do the following operation. Choose a building, and destroy its uppermost floor with cost h. Where h is building's height before removing the floor. You can do this operation any number of times but total cost should be less than or equal to K. Since you don't like tall buildings you want to decrease their heights. You have to minimise the maximum height of buildings and report this height (height of tallest among them after operations).

(Use long long data type instead of int to avoid overflow errors)

Input Format

T 
N1 K1 
a1 a2 a3 ..... aN1 
N2 K2 
a1 a2 a3 ..... aN2 . 
. 
. 
NT KT 
a1 a2 a3 ..... aNT

Constraints

  • 1<=T<=1000 Number of test cases
  • 1<=N<=100000 Number of buildings
  • 1<=K<=10^15
  • 0<=ai<=1000000
  • Sum of N over all test cases is at most 200000.

Output Format

ans1 
ans2 
ans3 
. 
. 
. 
ansT

Sample Input 0

3 
5 23
1 3 2 4 5
5 3000000
0 1000000 2 5 99999
3 9
3 3 3

Sample Output 0

2
999997
2

Here we can only use the iostream library, so all the other functions needs to be written by me. In that case, for the T iterations in a while loop, we are first taking in a an array followed by merge sorting the algorithm before proceeding to the helper function.

In the helper function we are trying to introduce recursion with the fact that as long as K is greater than the tallest building, it is going to reduce K with the height of the tallest building and reduce the top floor by 1.

In case the K is greater than equal to the height of the tallest building, it reduces the height of the tallest building by 1, and sorts the array of building heights and updates the value of accordingly. Finally it return the height of the tallest building if K falls below the same.

My code is:

#include <iostream>
using namespace std;

void merge(long long array[], int const left, int const mid,
           int const right)
{
    int const subArrayOne = mid - left + 1;
    int const subArrayTwo = right - mid;

    auto *leftArray = new int[subArrayOne],
         *rightArray = new int[subArrayTwo];

    for (auto i = 0; i < subArrayOne; i++)
        leftArray[i] = array[left + i];
    for (auto j = 0; j < subArrayTwo; j++)
        rightArray[j] = array[mid + 1 + j];

    auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;
    int indexOfMergedArray = left;

    while (indexOfSubArrayOne < subArrayOne
           && indexOfSubArrayTwo < subArrayTwo) {
        if (leftArray[indexOfSubArrayOne]
            <= rightArray[indexOfSubArrayTwo]) {
            array[indexOfMergedArray]
                = leftArray[indexOfSubArrayOne];
            indexOfSubArrayOne++;
        }
        else {
            array[indexOfMergedArray]
                = rightArray[indexOfSubArrayTwo];
            indexOfSubArrayTwo++;
        }
        indexOfMergedArray++;
    }
    while (indexOfSubArrayOne < subArrayOne) {
        array[indexOfMergedArray]
            = leftArray[indexOfSubArrayOne];
        indexOfSubArrayOne++;
        indexOfMergedArray++;
    }
    while (indexOfSubArrayTwo < subArrayTwo) {
        array[indexOfMergedArray]
            = rightArray[indexOfSubArrayTwo];
        indexOfSubArrayTwo++;
        indexOfMergedArray++;
    }
    delete[] leftArray;
    delete[] rightArray;
}

void mergeSort(long long array[], int const begin, int const end)
{
    if (begin >= end)
        return;

    int mid = begin + (end - begin) / 2;
    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

long long minimizeMaxHeight(long long heights[], int N, int K){
    if(K<0) return heights[N-1]+1;
    if(K==0) return heights[N-1];
    if(K>0){
        if(heights[N-1]>=heights[N-2]){
            heights[N-1] = heights[N-1]-1;
            return minimizeMaxHeight(heights, N, K-heights[N-1]);
        }
        else{
            mergeSort(heights, 0, N - 1);
            return minimizeMaxHeight(heights, N, K);
        }
    }
    return 0;
}

long long solve(long long heights[],int n,int k){
    
    //Recursive solution
    if(heights[n-1]<=k){
        heights[n-1]-=1;
        mergeSort(heights,0,n-1);
        return solve(heights,n,k-heights[n-1]);
    }
    return heights[n-1];
    
}

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        int N;
        long long K;
        std::cin >> N >> K;

        long long heights[N];
        for (int i = 0; i < N; ++i) {
            std::cin >> heights[i];
        }mergeSort(heights, 0, N - 1);
        long long ans = solve(heights, N, K);
        std::cout << ans << std::endl;
    }
    return 0;
}

The above is the recursive approach and there's another iterative approach which I'm trying:

#include <iostream>
using namespace std;

int main() {
    int T;
    std::cin >> T;
    while (T--) {
        int N;
        long long K;
        std::cin >> N >> K;
        long long total[1000001] = {0};
        long long heights[N];
        for (int i = 0; i < N; ++i) {
            std::cin >> heights[i];
            total[heights[i]]++;
        }
        long long ans = 0;
        for(int i = 1000000; i>0;){
            if(total[i]==0) {
                i--;
                continue;
            }
            else if(total[i]>0&&K>=i){
                total[i]--;
                total[i-1]++;
                K=K-i;
            }
            else if(total[i]>0&&K<i) {
                ans = i; 
                break;
            }
        }
        std::cout << ans << std::endl;
    }
    return 0;
}

For the recursive approach the code run only for one test case and for the iterative approach the code fails for two test cases.

For all the failed test cases in both the recursive and the iterative approach the issue is: Time Limit Exceeded

\$\endgroup\$
2
  • \$\begingroup\$ @TobySpeight thank you so much. I just added a new code which works and this time I'm encountering a TLE erros\r \$\endgroup\$
    – driver
    Aug 20, 2023 at 11:42
  • 3
    \$\begingroup\$ Thanks for adding the working code. I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Please check that I haven't misrepresented your code, and correct it if I have. \$\endgroup\$ Aug 20, 2023 at 11:50

1 Answer 1

7
\$\begingroup\$

Algorithm

You remove one floor from one building at a time. The complexity of the (iterative) code is therefore proportional to the total amount of floors, which is prohibitive. Better think this way:

Let's say the tallest building has a height \$H_0\$, and there are \$N_0\$ of them. The next tallest building has a height \$H_1\$, and there are \$N_1\$ of such buildings. To equalize heights, you have to remove \$H_0 - H_1\$ floors by the cost of

\$C = (H_1 + 1) + (H_1 + 2) + ... + H_0 = (H_0 - H_1)*(H_0 + H_1 + 1)/2\$

(do you see an arithmetic progression?) from \$N_0\$ building, giving the total cost of \$T = C * N_0\$. If you cannot afford this, you are done. If you can, you end up with \$N_0 + N_1\$ buildings of height \$H_1\$. Adjust the balance: \$K = K - T\$, and keep going.

To be really effective, you need a bit more elaborate data structure, a (sorted) list of pairs height, number.

Review

  • using namespace std is a very poor practice. Besides, you use std:: prefix anyway.

  • There is no need for heights array. You never use it. One long long variable is just enough.

  • More whitespaces please. total[i]>0&&K>=i is barely readable. Consider (total[i] > 0) && (K >= i)

  • There is no need to test for total[i] > 0 in the else/else if branches.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.