Menu Sidebar
Menu

June 2021

Codeforces Round #728 (Div. 2)B. Pleasant Pairs

给一个数组, 求两个数字相乘等于index想加的pair的个数. 因为是index想加, 所以已知index的大小是从3(1+2)到2*n. 我们就按个找每个数, 看看有多少pair. 因为A[i]*A[j]=[1,2*n], 那么就知道其中一个是的范围肯定是[1, sqrt(n)]. 所以只要是i能整除j的, 都是答案的可能性.

Codeforces Round #727 (Div. 2)D. PriceFixed

给N个pairs, 里面第一个数字是需要买几个, 第二个数字是买多少个后可以有优惠价格. 问花多少钱能买够所有需要买的物品. 因为每个物品价格都是一样的,相当于二元店, 买够第一个数字就变成了一元店. 那么我们想花最少钱, 肯定要买最多的打折物品, 但是打折物品需要买够两元的物品才能买, 所以我们按照从小到大的顺序排序好打折物品需要买多少才能买. 然后我们设买够n个物品后, 可以开始买打折物品, 因为我们知道如果买n个可以, 那么买n+1也可以, 所以问题转化成为如何找到n的lower_bound. 这里用二分查找, 方法check就是验证是否存在n个打折物品的可能. 验证方法如下, 假设total是一共要买的物品, 我们知道total-n, 就是没有当前状态下没有打折的物品的数量. 那么我们从最少的需要物品数量就可以买打折物品的物品开始, 如果当前物品的需要购买数量已经大于total-n, 就证明当前这个不能拿了, 于是我们因为拿不到n个物品, 所以return false. 如果当前物品的需要购买数量小于等于total-n, 就证明当前这个可以拿, 我们把它加进来变成total-n+A[i].first, 然后n -= A[i].first, 这样一直找下去, 直到n==0.

Codeforces Round #727 (Div. 2)A. Contest Start

设计一个比赛, 一共n个人, 每个人是固定时间间隔后开始比赛, 然后比赛的总长度是k, 求每个人的比赛的时候, 有多少人还没有完成比赛. 这题画画图就明白了, 但是要注意几个corner cases. 比如间隔给的长度小于比赛的长度等.

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.