专栏文章
p3460 sol(POI2007 TET)
题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqqni7w
- 此快照首次捕获于
- 2025/12/04 09:09 3 个月前
- 此快照最后确认于
- 2025/12/04 09:09 3 个月前
由于本题难以设计状态,考虑贪心。
考虑从低往顶扫,每次遇到前面有的就暴力消掉,并动态更新其他位置的距离,使用树状数组。
考虑证明这个贪心。重编号节点,每个节点按照其从低到顶出现的顺序从小到大编号,那么每次操作都可以消除一个逆序对。
由于将两个数完全消除不会导致去除任何的逆序对,所以每次操作不会有浪费,所以是最优的。
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...