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 ..... aNTConstraints
- 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 . . . ansTSample Input 0
3 5 23 1 3 2 4 5 5 3000000 0 1000000 2 5 99999 3 9 3 3 3Sample 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
