给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.

给一个数组, 求加入n个数字(大小不限)后, 使得数组中两个的差不大于k. 求n是多少. 这题贪心, 就是每次都取加入最大的数字.

给一个string,和一些query, 求每个query中, string展开后的长度. 这题就是pre sum. 秒了

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

给一个数组, 可以加n个非负数数字, 让他的算术平均数等于项数. 问n是几? 这题题中给了已知永远有答案, 所以想了想就知道, 是比较sum和项数. 因为我们加的是非负数,所以可以加0来在不增加算术平均数的情况下, 增加项数.

给两个数字l和r, 求从l加到r中间digit的变化个数是多少. 这题用的方法和D一样,就是先求R的答案, 然后减去L的答案, 具体的求法是通过观察: 比如21这个数, 从1->9 是9个1位改变, 9->10是1个2位, 10->19是9个1位改变, 19->20是2个1位改变. 20->21 是1个1位改变, 所以加起来就是21+2, 有次可推,数字123是123+12+1.

给三个数,a,b,k, 问a和b是不是能在k次(exactly) 下通过整除相等. 这个题情况比较多, 比如a和b互质, 比如k大于a和b. 反正就是交一次就对的都是大神. 这题思路是, 反正a和b一直和某数做整除, 最后就是1, 肯定相等啊, 所以只需要计算有多少质因子在a和b的和中.即可, 剩下就是各种corner cases.

给一组数和l还有r, 求这组数中任意两个数的和在[L,R]中. 先排序, 然后求[0,R], 然后再求[0,L-1], 两个相减即可.

给一个数组, 可以从两端取数字, 取了就没了, 求最少多少步可以取了最大和最小值. 这题他妈的真费时间, 一共3种取法 (答案给的是四种), 反正我三种做的, 三种是: 从左往右取, 从右往左和两侧取. 这题给了最大值是n, 最小值是1, 所以1/2两种都很好做, 就是第三个, 需要找下两个值的坐标, 然后减去两端就行了.

给一个字符串s, 求字典序最小的字符串没有在s中出现. 这题就是bfs按个试..妈的, 比赛的时候想多了. 浪费时间