「CF1251X」Educational Codeforces Round 75

2019年10月26日2770

A. Broken Keyboard

如果有一个字母连续出现奇数次,则它是正常的,模拟

B. Binary Palindromes

由于可以随意交换,那么优先把短的 string 变成回文,需要消耗 len / 2 对字符

C. Minimize The Integer

最后能得到的字符串满足 所有奇数的相对顺序不变 且 所有偶数的相对顺序不变,从左到右依此贪心

D. Salary Changing

二分中位数 mid,按薪水左端点排序

左端点从大到小考虑,让前 n / 2 + 1 个人 薪水 >= mid,其它人取左端点,并判断合法性

E2. Voting (Hard Version)

这个贪心很不好想,按 m 排序,可以算一下比每个人 m 更大的那些人中,至少要贿赂多少人

假设排序后的 m 序列是 1 3 3 4 5 7 7 7

令 b_i = m_i – i + 1,即 1 2 1 1 1 2 1 0,表示说,第 i 个人往后的人里,至少要贿赂 b_i 个人

从右往左,维护一个 multiset,贿赂最便宜的人

avatar
  Subscribe  
提醒