CF1809D Binary String Sorting 题解

发布时间 2023-12-06 18:46:21作者: ShawyYum

题意:

思路:

贪心:

单调不降的 $ 01 $ 字符串,一定是一串连续的 $ 0 $ 再加上一串连续的 $ 1 $ 。由于每次操作的代价很大,所以需要在操作次数尽可能少的情况下,尽可能多地使用交换操作

由于 $ 1 $ 次交换操作,只能减少 $ 1 $ 个逆序对,当存在多个逆序对时,优先通过删除操作减少逆序对的数量,来减少逆序对的数量。当逆序对的数量减少到 $ 1 $ 时,此时再采取 $ 1 $ 次交换操作,即为最优策略;当逆序对的数量减少到 $ 0 $ 时,此时无需进行任何操作,即为最优策略。

因此,枚举 $ 01 $ 分界线。在分界线同一侧进行交换操作是无意义的,那么,分界线左侧的 $ 1 $ 全部删除,分界线右侧的 $ 0 $ 全部删除。注意到,分界线左侧第一个字符为 $ 1 $ 且分界线右侧第一个字符为 $ 0 $ 时, $ 1 $ 次交换操作优于 $ 2 $ 次删除操作,此时优先执行交换操作,即为最优策略。