在 C/C++ 中如何对二进制字符串进行排列以在指定索引范围内获得最大值？

假设给定一个仅包含 0 和 1 的字符串，我们有 M 个不重叠的范围 A、B（A <= B），更具体地说是 [A1, B1]、[A2, B2]、…、[AM, BM]。这些区间中的任意两个都不重叠——正式地说，对于每个有效的 i、j，如果 i!=j，则要么 Ai

任务是找到一个合法的或有效的排列，该排列将同时满足以下两个条件：

  • 所有 M 个给定范围内的数字之和最大。

  • 字符串在字典序上最大。字符串 1100 在字典序上高于字符串 1001。

示例

Input
11100
3
3 4
5 5
Output
00111
First we put 1’s in position 3 and 4 then in 5 as there are no 1’s left, the string formed is 00111.
Input
0000111
2
1 1
1 2
Output
1110000

在上面的例子中，我们首先在第 1 和第 2 个位置放 1，然后我们还有另一个 '1' 剩余，

因此，我们用它来在字典序上最大化字符串，并将它放在第 3 个位置，从而完成重排。

更新于： 2020年1月29日

225 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告