核心思路:要让删除的天数最少,需保留尽可能多的天数。最优策略是将数组排序(排序后相邻元素差值最小,能最大化满足条件的连续天数),然后找到排序后数组中最长的连续子数组(其中相邻元素的绝对差≤k)—— 因为排序后该子数组可直接按顺序排列,满足 “任意连续两天差值≤k” 的条件。最终最少删除天数 = 总天数 n - 最长满足条件的子数组长度。
注册一个 南阳理工学院OJ 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 南阳理工学院OJ 通用账户