- csp-s模拟赛13
T1 我的思路(反悔贪心)
- @ 2026-10-5 18:42:43
首先,每个位置优先选大的,并且每个位置记录一下当前能量值 ,考虑哪些选B的地方可以反悔,于是开始思考:如果不行,那说明这次修改会使得后面某个位置的能量值小于 了,所以只要这次修改不会发生这种情况就能行。也就是说,记当前修改和之前的修改导致能量减少了 ,只要不存在 ,变形一下 这次就可以修改,而这些 之中最弱的就是最小值,所以建立 ,每次决策检查一下 ,如果是就可以改,不是就不行。
时间复杂度
3 条评论
-
100002 Elite LV 10 @ 2026-10-5 19:52:38已修改根据字典序性质,此题不需要反悔贪心,直接贪心,在 b[i]>a[i] 的情况下能选A则就选A即可,从前往后遍历只要能修改那就一定是最优解。 具体做法就是维护两个类似后缀最小值的数组,然后记一个变量,只要当前可以修改那么我永久增加此变量的值,不断判断就行
❤️ 3 -
@ 2026-10-5 18:48:38qyl,李文越也是有点类似这样做好像。其它人是倒着做
-
@ 2026-10-5 18:44:59神秘无解边界卡我一个点
- 1