给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是多少. 这题贪心 就是每次都取加入最大的数字.
设计一个比赛 一共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.
给三个数abk 问a和b是不是能在k次(exactly) 下通过整除相等. 这个题情况比较多 比如a和b互质 比如k大于a和b. 反正就是交一次就对的都是大神. 这题思路是 反正a和b一直和某数做整除 最后就是1 肯定相等啊 所以只需要计算有多少质因子在a和b的和中.即可 剩下就是各种corner cases.
给一个数组 可以从两端取数字 取了就没了 求最少多少步可以取了最大和最小值. 这题他妈的真费时间 一共3种取法 (答案给的是四种) 反正我三种做的 三种是: 从左往右取 从右往左和两侧取. 这题给了最大值是n 最小值是1 所以1/2两种都很好做 就是第三个 需要找下两个值的坐标 然后减去两端就行了.