首页 > Greedy Gift Takers
开通博客写题解
头像 在提需求的海螺很想退休
发表于 2023-06-28 16:59:26
1.把原始奶牛队列可以分成，左边：可获得礼物奶牛，右边：不可获得奶牛。例，以“|”为分隔符有 ，1 2 3 4 | 5 6 7 8 9 ，即左边1 2 3 4，右边5 6 7 8 9.为什么可以分成两边。 为什么可以分成两边？ 以上述例右边证明，如果 6 可获得礼物则 5 必然可 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 在刷题的单身狗很开心
发表于 2023-09-08 15:13:10
首先可以看出是按照奶牛的编号进行二分去寻找第一个没有礼物的奶牛。但如何验证某个编号的奶牛前面有死循环存在呢。 因为是从后面插空的所以会因为后面牛数量的改变而改变。但可以转化到插第几个位置，如果位置2上有两个及其以上的牛的目标都是它，那么就会造成死循环。同样如果3这个位置上有三个及其以上的牛目标 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 WAWA鱼
发表于 2022-03-15 11:10:34
思路： 首先我们可以发现，如果第x个牛不能拿到礼物，则x之后的所有牛都不能拿到礼物，则区间具有单调性，可以想到用二分来解决 然后思考怎么写判断条件 我们需要知道一个结论： 怎么样会形成一个死循环呢？如果出现在前i个位置的牛多于i个，则这i个牛就会一直卡在这前i个位置，我们预处理出小于二分值位置的数量 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”