Codeforces Round #709 Basic Diplomacy 贪心

题意

有n朋友, 有m天。张三每天要找一个朋友玩。问能不能找到一种找法,让每个朋友最多被找(m/2,向上取整)次。


题解

自古贪心看证明。

首先,人分两类。

一类,总共出现的天数就不超过m/2的,优先选择。这类人,只管选,怎么选都不会超。

二类,出现天数超过m/2的。因为前面第一类已经占了一些天。所以剩下的天数,至少有一个二类人,且不会存在一类人。

假设二类人只有1个,那就对剩下的天数尽量铺就完了。铺不满就是NO,铺满了就是YES。

假设二类人多于1个。因为没有一类人,那其实一定有解的。因为是m/2向上取整划分的两类人,所以一人一半就完事。优先解决剩下的天里面,能用的二类人少的天数就可以了。


可疑的解

上面的解写起来太麻烦了,就随手写了这个解试了一发,居然就过了。

对天进行排序,人数少的天排前面,认数多的排后面。然后扫一遍,优先选择剩余可用选择次数少的人。

也就是,第一优先级是那天的人数,第二优先级是可选次数。

剩余可用选择次数少的人=MIN(m/2-已被选择的次数,总可选天数-已被选择的次数)。

这个解法依赖于排序,如果把一堆只有一个二类人的天排在前面,可能导致二类人反而先于一类人被消耗。

比如二类人在前面先烧到只剩1的可用次数,且剩余的那一天,这个二类人是和剩余次数为2的一类人。结果这个二类人会优先于一类人被消耗。


代码

我反正觉得我代码是错的,可能是数据弱。

Submission #110985004 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论