gpt4 book ai didi

c++ - 找到堆栈的最大高度,使其对于所有三个堆栈都相等

转载 作者:行者123 更新时间:2023-12-04 11:39:14 26 4
gpt4 key购买 nike

我们有三叠圆柱体,每个圆柱体的直径相同,但它们的高度可能不同。我们可以通过多次移除和丢弃其最顶部的圆柱体来更改堆栈的高度。
找出堆栈的最大可能高度,使所有堆栈的高度完全相同。这意味着您必须从三个堆栈中的零个或多个顶部移除零个或多个圆柱体,直到它们都具有相同的高度,然后返回高度。
例子:

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 作为答案。
我的方法
我数了 sum1stack1 sum2stack2sum3stack 3然后开始减少 greatest sum 减去它的值topmost element 该堆栈的 && popping it out 然后迭代使用 while(sum1!=sum2 || sum2!=sum3 ||sum3!sum1) .但是我的 while 循环最多成功执行了 2 个条件语句,之后它继续处理而不给出输出,看起来它进入了无限循环,但我已经包含了终止循环的所有条件。我的方法有什么问题,请帮忙,非常感谢。
我的代码;
#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;
}

最佳答案

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

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

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

    关于c++ - 找到堆栈的最大高度,使其对于所有三个堆栈都相等,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68224504/

    26 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com