复盘｜第110场双周赛
来源:哔哩哔哩
发布时间：2023-08-09 18:34:12
(资料图片仅供参考)
取整购买后的账户余额
【数学】题目的意思是吧purchaseAmout的各位数四舍五入，可用如下公式计算⌈(purchaseAmout + 5) / 10⌉ × 10。
在链表中插入最大公约数
【模拟】遍历链表，在当前节点cur后面插入gcd节点，gcd节点指向cur的下一个节点。插入后，cur更新位，循环直到cur没有下一个节点为止。
使循环数组所有元素相等的最少秒数
【枚举】最后所有元素一定是在nums中的数，枚举这个数记为x。看作是x扩散到左右两个为止，多个位置的相同的数字x同时扩散，扩散完整个数组的耗时取决于相距最远的两个相邻的x。设这两个x的下标分别为i和j，且i<j，耗时为⌊(j - i) / 2⌋，取所有耗时的最小值即为答案。用哈希表pos存每个数字的下标集合，遍历下标i时在哈希表中添加i+n拼成非环形数组。
使数组和小于等于 x 的最少时间
【贪心 + 排序 + DP】显然，每个下标i至多操作一次，操作多次可以只保留最后一次（前面的操作是多余的），所以至多操作n次，尝试枚举答案。考虑第t秒元素之和最小是多少，如果从一开始到第t秒不做任何操作，元素之和等于sum(num1) + sum(nums2) t，用它减去这些元素减少量之和的最大值就是第t秒元素之和的最小值。假设已经选好了要操作的元素，那么nums2[i]越大，操作的时间应该越靠后，根据排序不等式，在第t秒，sum(num1) + sum(nums2) t的减少量的最大值相当于求解：按照nums2[i]从小到大排序后，从nums1中训责一个长为t的子序列，子序列的第j个数的nums2[j]的系数为j，计算减少量的最大值。设子序列的第j个数（j从1开始）的下标为i，它对减少量的贡献是nums1[i] + nums2[i] j，用dp解决。定义f[i + 1] [j]表示从前i个数中选出j个数，减少量最大是多少，用“选或不选的思路”，有f[i + 1] [j] = max(f[i] [j], f[i] [j - 1] + nums1[i] + nums2[i] j)。
x
