返回
多御红包活动

CodeForces 777E Hanoi Factory

发布时间:2022-11-28 20:17:18 45

题目链接:​​http://codeforces.com/contest/777/problem/E​​​
题意:叠汉诺塔,问你最高能叠几层,给你n个圆环,每个圆环告诉你内径和外径,还有他的厚度,要叠起来的条件是,上面圆环的外径,小于下面圆环的外径,且大于下面圆环的内径。问你最高能叠多高?
解析:先把圆环按外径从大到小排个序,由于越往上走内径越小,所以先把内径大的圆环用了,所以如果外径相同,就把内径也从大到小排个序,由于叠圆环的过程很像栈的操作,所以可以用栈来维护

#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e5+100;
struct node
{
int a,b;
int h;
bool operator <(const node &t)const
{
if(b==t.b)
return a>t.a;
return b>t.b;
}
}a[maxn];
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d %d %d",&a[i].a,&a[i].b,&a[i].h);
sort(a,a+n);
stacks;
s.push(a[0]);
long long sum = a[0].h,ans = a[0].h;
for(int i=1;i<n;i++)
{
while(!s.empty() && a[i].b<=s.top().a)
{
sum -= s.top().h;
s.pop();
}
sum += a[i].h;
ans = max(ans,sum);
s.push(a[i]);
}
printf("%I64d\n",ans);
return 0;
}

 

特别声明:以上内容(图片及文字)均为互联网收集或者用户上传发布,本站仅提供信息存储服务!如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争,网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线