时间戳

首页 > 解决方案 > 找到堆栈的最大高度，使得所有三个堆栈都相等

c++ - 找到堆栈的最大高度，使得所有三个堆栈都相等

问题描述

我们有三组圆柱体，每个圆柱体的直径相同，但它们的高度可能不同。我们可以通过多次移除和丢弃最上面的圆柱体来改变堆栈的高度。

找到堆栈的最大可能高度，以使所有堆栈的高度完全相同。这意味着您必须从三个堆栈中的零个或多个顶部移除零个或多个圆柱体，直到它们都具有相同的高度，然后返回高度。

例子：

h1 = [3, 2, 1, 1, 1] //remove 3 , it will make height 5 i.e (1+1+1+2=5);

h2 = [4, 3, 2]       //remove [4] it will make height 5;

h3 = [1, 1, 4, 1]    //remove [1,1] it will make height 5;

它将返回 5 作为答案。我的方法我计算sum1了stack1 sum2forstack2和sum3forstack 3然后开始通过用那个堆栈的 &&greatest sum减去它来减少值，然后迭代地使用. 但是我的while循环成功执行了最多2个条件语句，之后，它继续处理而不给出输出，它似乎进入了无限循环，但我已经包含了所有条件来终止循环。我的方法出了什么问题，请帮忙，非常感谢。topmost elementpopping it outwhile(sum1!=sum2 || sum2!=sum3 ||sum3!sum1)

我的代码；

#include<iostream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
int main(){
    vector<int>h1={3,2,1,1,1};
    vector<int>h2={4,3,2};
    vector<int>h3={1,1,4,1};
    int sum1=0,sum2=0,sum3=0;
    stack<int>s1,s2,s3;
    for(int i=h1.size()-1;i>=0;i--){
            s1.push(h1[i]);
            sum1+=h1[i];
        }
    for(int i=h2.size()-1;i>=0;i--){
            s2.push(h2[i]);
            sum2+=h2[i];
        }
    for(int i=h3.size()-1;i>=0;i--){
            s3.push(h3[i]);
            sum3+=h3[i];
        }
        while(sum1!=sum2 || sum2!=sum3 ||  sum3!=sum1){
        vector<int>sum;
        sum.push_back(sum1);sum.push_back(sum2);sum.push_back(sum3);
        sort(sum.begin(),sum.end(),greater<int>());
        if(sum1==sum[0] && sum2!=sum[0] && sum3!=sum[0] && !s1.empty()){
            sum1=sum1-s1.top();
            s1.pop();
            cout<<sum1<<endl;
            cout<<s1.top()<<endl;

        }
        if(sum2==sum[0] && sum3!=sum[0] && sum1!=sum[0] && !s2.empty() ){
            sum2=sum2-s2.top();
            s2.pop();
            cout<<sum2<<endl;
            cout<<s2.top()<<endl;
        }
        if (sum3==sum[0] && sum2!=sum[0] && sum3!=sum[0] && !s3.empty()){
            sum3=sum3-s3.top();
            s3.pop();
            cout<<sum3<<endl;
            cout<<s3.top();
            //h3.pop_back();
        }
        if (sum1==sum[0] && sum2==sum[0] && sum3!=sum[0] && !s1.empty() && !s2.empty()){
            sum1=sum1-s1.top();sum2=sum2-s2.top();
            s1.pop();s2.pop();
            //h1.pop_back();h2.pop_back();
        }
        if (sum1!=sum[0] && sum2==sum[0] && sum3==sum[0] && !s2.empty() && !s3.empty()){
            sum2=sum2-s2.top();sum3=sum3-s3.top();
            s2.pop();s3.pop();
            //h2.pop_back();h3.pop_back();
        }
        if (sum1==sum[0] && sum2!=sum[0] && sum3==sum[0]  && !s1.empty() && !s3.empty()){
            sum1=sum1-s1.top();sum3=sum3-s3.top();
            s1.pop();s3.pop();
            //h1.pop_back();h3.pop_back();
        }
    }
    cout<<"ans"<<sum1;
}

标签： c++algorithmvectordata-structuresstack

解决方案

一种方法是使用最大堆。如果最大堆的顶部堆栈的总和等于总和的最小值，则完成。

算法 ：

  1. 计算每个堆栈中元素的总和并跟踪最小值。
  2. 将每个堆栈作为 (index_of_the_stack, current_sum_of_the_stack) 之类的元组添加到最大堆，其中 sum 作为比较器。
  3. 如果最大堆的顶部堆栈的总和等于最小总和，那么您就完成了。
  4. 否则删除堆的最大堆栈 - 通过删除最大堆栈我的意思是删除元组（索引，总和）
  5. 然后继续从具有该索引的堆栈中删除元素，直到其总和小于或等于最小总和。
  6. 将最小总和更新为 minimum_sum = min(minimum_sum, sum_of_updated_top_stack)
  7. 将元组 ( index, updated_sum_of_the_stack ) 添加回堆中。
  8. 转到第 3 步。

这应该处理任意数量的堆栈。

推荐阅读