请选择 进入手机版 | 继续访问电脑版

【Nowcoder】牛客小白月赛26 H 保卫家园 | 贪心、扫描线

[复制链接]
林雨宣 发表于 2020-12-31 18:56:42 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
emmm…测验周一天一套小白月赛保持手感…
别问为什么,怕被太难的题卡的挂科…
原来不想写什么题解,不外这题确实有妙处,就记载一下吧
题目大意:

为了反抗深渊的蔓延,被深渊毁掉故里的人们组建法兰不死队来镇压深渊。已知法兰不死队的最大体例为                              k                          k               k,即队伍最多能有                              k                          k               k人。有                              n                          n               n个人想加入不死队,他们每人都有一个盼望入伍时间                              s                          s               s和退役时间                              t                          t               t。入伍时间表示这个人如果要入伍的话只能在                              s                          s               s时刻入伍。退役时间代表这个人可以在t时刻退却伍。因为战况严峻,所以队伍必须一直保持到达最大体例的状态。即队伍到达最大体例时候,队伍里有人可以退役的话,如果没有人来接替这个人的位置就不能退役。问最少有多少人没有进入法兰不死队的履历。
注:同一时刻,允许多个人一起入伍大概退伍,退伍时间要严格大于                              t                          t               t
该人是否入伍是你来决定的 即就算没到达最多体例人数                              k                          k               k,到了某人的入伍时间,你可以选择不让他入伍
题目思路:

按照题解所说,可以抽象一下:
选出最多的线段,使的数轴上的每个点被线段覆盖不高出k次
可以把线段覆盖想成区间覆盖问题,当前点被哪些线段覆盖到。之后,可以把以该点作为起点的线段放进到扫描线组成的集合里,但是放入的过程中要思量一下,如果当前点覆盖高出k次了,应该让哪个线段出去,贪心的思量,一定会让竣事时间大的先出去,因为会淘汰反面空间的浪费,既然出去了,那么这个就不会入伍了,也就可以记载答案了。
贪心的好题(G)
Code:

[code]/*** keep hungry and calm CoolGuang!  ***/#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")#pragma GCC optimize(3)#include #include#include#include#include#include#define debug(x) cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

发布主题

专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )