SpaceWarDiv1

作者： 权大磊 钟知闲 徐明宽

关键字： 二分 贪心

题目描述

给出$n$个美少女， 每个美少女有一个战斗值 $MagicalGirlStrength$， 又给出 $n$ 组敌人， 每组敌人的战斗值为 $EnemyStrength$， 每组敌人人数为 $EnemyCount$， 若一个美少女战斗值大于等于一个敌人战斗值就可以打败他，同时该美少女疲劳值 $+ 1$， 最小化打败所有敌人的后的最大疲劳值，若不能击败所有敌人，返回 $-1$。

数据范围： $n ≤ 50, Strength ≤ 10000, Count ≤ 100000000000000({10}^{14})$。

时间限制： $2s$

空间限制： $64M$

算法一

现在要最小化最大值， 这个最大值也存在单调性， 于是可以二分， 判断方法只需要将敌人按照从小到大排序，美少女按战斗值从小到大排序。若敌人战斗力最大值大于美少女最大战斗值，无解；有解时，贪心从强到弱依次用小于二分值次的美少女去从强至弱的击败敌人， 若可以， 二分更小，若不行，二分更大。

注意二分上界至少应设为 $U=\sum_{i=0}^{n-1}\mathrm{EnemyCount}[i]$。可以一开始先排好序，在二分判定时做到 $O(n)$ 的复杂度。

时间复杂度 ： $O( n \log U )$

算法二

我们一定可以让战斗值最大的美少女的疲劳值与最大疲劳值相同（否则可以交换一些美少女打的敌人使得满足这个条件）。同理，我们一定可以让所有具有最大疲劳值的美少女的战斗值都大于等于其他美少女。所以，将美少女按战斗值从小到大排序后最大疲劳值一定可以出现在一个后缀中。当美少女$[0,i)$均无法击败某个敌人时，这个敌人就必须由美少女$[i,n)$这个后缀去击败——所有的这些条件构成了增加最大疲劳值的所有因素。

所以，将美少女和敌人都按战斗值从大到小排序后拿两个指针扫一遍，将所有的((敌人数量)除以(美少女数量)向上取整)取最大值就是答案（如果出现除以$0$的情况答案就是$-1$）。

时间复杂度：$O(n\log n)$，由于瓶颈是排序，所以可以用基数排序做到更好的复杂度。