首页 > 其他分享 >代码随想录 day35 柠檬水找零 根据身高重建队列 用最少数量的箭引爆气球

代码随想录 day35 柠檬水找零 根据身高重建队列 用最少数量的箭引爆气球

时间:2024-01-30 20:01:08浏览次数:15  
标签:边界 队列 随想录 找零 柠檬水 身高 气球

柠檬水找零

就根据几种条件列出来找零情况就行 生活经验可知 找零当然先给大面额的利于后面的找零

根据身高重建队列
image

这题感觉就是先做过队列给糖也难以有思路
这里是先按身高先排好队
一样身高就k小的排在前面
然后再按他前面有几个人直接就给他插到第几个位置就行

image

用最少数量的箭引爆气球
image

代码虽然很简单 但是非常难
这里的思路是将所有气球按一定顺序(这里是左边界)排好序
尽量对齐
然后如果相邻的两个气球不相交(i-1的右边界大于i的左边界) 那就是要多射一箭
默认count为1
相交的情况实际上把这两个气球相交的部分看成一个整体和下一个气球比较
由于两个气球的大小不固定 所以这个相交气球的右边界实际上是
根据两个气球更小的那个右边界决定的
image

标签:边界,队列,随想录,找零,柠檬水,身高,气球
From: https://www.cnblogs.com/mingtiao/p/17997848

相关文章