构造算法题目积累

cf1304D

题目给出n-1个‘<’‘>’约束，第i个位置的<意味着结果串中a[i]<a[i+1]，要求用1~n个数构造出两个串，分别拥有最小和最大的LIS。

思路：我们将升序1~n中连续>的区间执行reverse操作，执行完毕后的结果就是拥有最大LIS的满足约束的结果串。

证明：这种方法利用了全部的上升区间，及下降区间的一侧边界。我们知道对于连续下降区间，最多只能有一个元素被选入LIS，因此整体利用率达到最大。

最短的类似，首先降序n~1，然后不满足约束的reverse。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

for(int i=0;i<n;i++)
    ans[i]=i+1;
l=0,r=0;
for(int i=0;i<n-1;i++){
    if(cst[i]=='>'){
        r=i+1;
    }else{
        if(l<r)
            reverse(ans+l,ans+r+1);
        l=i+1;
    }
}
if(l<r)
    reverse(ans+l,ans+r+1);
for(int i=0;i<n;i++){
    printf("%d%c",ans[i],(i==n-1?'\n':' '));
}
全部评论

相关推荐

11-26 01:19
内蒙古大学 电路设计工程师
点赞 评论 收藏
分享
11-24 12:23
快手_电商_支付技术(实习员工)
分享一下我的日常实习经历
bg中下流211本，26后端选手欢迎大佬们与我多多交流，互相学习~美团&nbsp;-&nbsp;火车票供应链组一面（7.3），第一次面大厂，很激动紧张，答出来80%，还是挂了字节&nbsp;-&nbsp;火山引擎一面（8.1），都答上来了，反馈说26届不适合业务对接，估计没hc了，但是hr说面评很好小米&nbsp;-&nbsp;一面（8.1），面试官评价很好阿里&nbsp;-&nbsp;高德地图（8.2），被狠狠拷打了，疯狂问，一直问到不会为止，还是自己太菜了小米&nbsp;-&nbsp;二面（8.2）oc快手&nbsp;-&nbsp;商业化一面（8.8）快手&nbsp;-&nbsp;商业化二面（8.9）oc字节&nbsp;-&nbsp;Data（8.12），计网操作系统场景题，一道mid，一道hard，mid手撕出来了，对于hard（课程表，方法是...
点赞 评论 收藏
分享
11-01 19:18
蚌埠坦克学院 智能驾驶系统工程师
不是哥们
这面试时间是认真的吗😰
Natrium_：这时间我以为飞机票
点赞 评论 收藏
分享
10-25 12:05
已编辑
湖南科技大学 Java
难得的HR态度
BOSS上头一次碰到这样的HR，太难得了 #hr#
若梦难了：我有你这简历，已经大厂乱杀了
点赞 评论 收藏
分享
头像
11-28 17:23
武汉大学 C++
华为（算法工程师）
时间线7.29&nbsp;--&nbsp;投递8.28&nbsp;--&nbsp;笔试（200+/600飘过）8.31&nbsp;--&nbsp;测评9.14&nbsp;--&nbsp;一面9.26&nbsp;--&nbsp;线下二三面最终结果：应该是寄了，对接人主动降温，建议我签一个保底。只能说大概率是一面面评抽象了，无缘华为了一面（50min左右）抽象至极的一面，面试官感觉完全不懂SLAM，我说我是图优化框架，面试官问我图是怎么处理的呢。我说是指图有哪些节点么，面试官说“就是你的图是怎么处理的，图像处理”；然后线上手撕要求白纸写，复盘笔试不告诉你题让你自己想，讲了半天说你做的都是开发，真的有被抽象到，不过就这样都不挂，看来华子一面真不挂人二面（50min左右）二面线下面，明显感受好多了回...
查看6道真题和解析 华为求职进展汇总
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
235798次浏览 2038人参与
# ai智能作图 #
25561次浏览 298人参与
# 北方华创开奖 #
66618次浏览 550人参与
# 25届秋招总结 #
404871次浏览 4061人参与
# 25届机械人为了秋招做了哪些准备？ #
25831次浏览 361人参与
# 地方国企笔面经互助 #
6780次浏览 16人参与
# 阿里云管培生offer #
61179次浏览 1755人参与
# 机械求职避坑tips #
23024次浏览 246人参与
# 实习，投递多份简历没人回复怎么办 #
2438445次浏览 34726人参与
# 软件开发投递记录 #
1480297次浏览 23940人参与
# 我的实习求职记录 #
6128185次浏览 83998人参与
# 我在牛爱网找对象 #
74650次浏览 554人参与
# 机械人怎么评价今年的华为 #
157577次浏览 1350人参与
# 歌尔求职进展汇总 #
42852次浏览 294人参与
# 如果再来一次，你还会选择这个工作吗？ #
113783次浏览 1130人参与
# 你觉得通信/硬件有必要实习吗？ #
54673次浏览 695人参与
# 如何写一份好简历 #
618447次浏览 8721人参与
# 在职场上，你最讨厌什么样的同事 #
5922次浏览 89人参与
# 如果可以，你希望哪个公司来捞你 #
32938次浏览 193人参与
# 虾皮求职进展汇总 #
87623次浏览 703人参与
# 硬件兄弟们 甩出你的华为奖状 #
78329次浏览 628人参与
# 你觉得第一学历对求职有影响吗？ #
17623次浏览 154人参与
牛客网
牛客企业服务