第 316 场周赛 | 解题报告 | 珂学家

珂朵莉

2908

2022.10.23

2022.10.25

发布于未知归属地

脑筋急转弯前缀和周赛技术交流珂朵莉

前言
整体评价
写在最后

前言

这么说来也对。威廉和她连彼此的名字都还不晓得。
「我叫威廉。请多指教，珂朵莉。」
一瞬间，珂朵莉「唔」地哽住呼吸。
「然后，呃，还有就是……」她摸索着如何开口。
「……没事。很抱歉打扰你，好好休息。」

整体评价

t3 枚举&前缀和，比较复杂，应该是我的解法复杂了。 t4脑筋急转弯，奇偶分组。

质量还可以，推荐。

快速通道：第316场周赛

更多解题报告详见：珂朵莉MM的解题报告汇总

T1. 判断两个事件是否存在冲突

6214. 判断两个事件是否存在冲突

这个就是求区间交集，是有套路的。
先把时间转换成数值
[x1, y1] 和 [x2, y2]

可以借助 max(x1, x2) <= min(y1, y2) 归一化

Java

class Solution {
    
    int convert(String s) {
        char[] t = s.toCharArray();
        int hour = (t[0] - '0') * 10 + (t[1] - '0');
        int miunte = (t[3] - '0') * 10 + (t[4] - '0');
        
        return hour * 60 + miunte;
    }

    public boolean haveConflict(String[] event1, String[] event2) {

        int s1 = convert(event1[0]), e1 = convert(event1[1]);
        int s2 = convert(event2[0]), e2 = convert(event2[1]);
        
        return Math.max(s1, s2) <= Math.min(e1, e2);
        
    }
    
}

T2. 最大公因数等于 K 的子数组数目

6224. 最大公因数等于 K 的子数组数目

区间的问题就是枚举，啥也别想了，就是 $O (n^{2})$

Java

class Solution {
    
    int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    
    public int subarrayGCD(int[] nums, int k) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int prev = nums[i];
            if (prev < k) continue;
            if (prev == k) {
                ans++;
            }
            for (int j = i + 1; j < n; j++) {
                prev = gcd(prev, nums[j]);
                if (prev == k) {
                    ans++;
                }
                // 这边用 prev % k != 0更好
                if (prev < k) break;
            }
        }
        
        return ans;
        
    }

}

T3. 使数组相等的最小开销

6216. 使数组相等的最小开销

方法一: 枚举+前缀和

这题有意思啊，不过我应该写了一个复杂版本的。

就是枚举数值v，让所有的值都变成v的代价，并求最小的值。

这里分两个部分， $< v$ 和 $> v$

先考虑 $< v$ 的情况

其代价为 $\sum (v - v_{i}) * cos t [v_{i}] ， (v_{i} < v)$

可以移项得到 $\sum v * cos t [v_{i}] - \sum v_{i} * cos t [v_{i}]$

所以这里面其实有两个前缀和

一个是 $\sum cos t [v_{i}]$ , 另一个是 $\sum v_{i} * cos t [v_{i}]$

考虑 $> v$ ,也是类似的做法

Java

class Solution {

    // 应该是枚举
    public long minCost(int[] nums, int[] cost) {

        int minV = Integer.MAX_VALUE, maxV = Integer.MIN_VALUE;
        for (int v: nums) {
            minV = Math.min(minV, v);
            maxV = Math.max(maxV, v);
        }

        // (x - i) * cost[i]
        // x * 累加cost[i] - 累加i*cost[i]

        long[] num2 = new long[maxV + 1];
        long[] cost2 = new long[maxV + 1];
        for (int i = 0; i < cost.length; i++) {
            num2[nums[i]]++;
            cost2[nums[i]] += cost[i];
        }

        long[] costSum = new long[maxV + 2];
        long[] costFx = new long[maxV + 2];

        for (int i = 0; i <= maxV; i++) {
            costSum[i + 1] = costSum[i] + cost2[i];
            costFx[i + 1] = costFx[i] + cost2[i] * i;
        }

        // 注意是long.max_value
        long ans = Long.MAX_VALUE;
        for (int i = minV; i <= maxV; i++) {
            long delta1 = i * costSum[i] - costFx[i];
            long delta2 = (costFx[maxV + 1] - costFx[i]) - i * (costSum[maxV + 1] - costSum[i]);

            ans = Math.min(delta1 + delta2, ans);
        }

        return ans;

    }

}

方法二: 三分(赛后补充)

需要严格的凸/凹函数保证才行，这个时候，可以借助这个求极值。

Java

class Solution {
    
    long compute(int[] nums, int[] cost, int val) {
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += (long)Math.abs(nums[i] - val) * cost[i];
        }
        return sum;
    }
    
    public long minCost(int[] nums, int[] cost) {
        
        int minV = Arrays.stream(nums).min().getAsInt();
        int maxV = Arrays.stream(nums).max().getAsInt();
        
        int ans = -1;
        int l = minV, r = maxV;
        while (l <= r) {
            int d = r - l;
            int p1 = l + d / 3;
            int p2 = r - d / 3;
            
            if (compute(nums, cost, p1) <= compute(nums, cost, p2)) {
                ans = p1;
                r = p2 - 1;
            } else {
                ans = p2;
                l = p1 + 1;
            }
        }
        
        return compute(nums, cost, ans);

    }
    
}

方法三: 点集增量(赛后补充)

把cost权重看重点的个数，那滑动的时候，维护左右两侧的点数就行。

每次增量计算，左侧累计加左侧点数 $l e f t A cc + = l e f tN u m$ ，右侧累计减右侧点数 $r i g h t A cc - = r i g h tN u m$ 。

$an s = M a t h . min (an s, l e f t A cc + r i g h t A cc)$

滑动的是值域，当然离散化的可以加速这个过程。

这应该是珂朵莉MM在比赛中，最初冒出来的解法，不过没有坚持。

Java

class Solution {
    
    // 模拟点集 整体 运动
    public long minCost(int[] nums, int[] cost) {
        
        long rightCost = 0, rightAcc = 0;
        for (int i = 0; i < nums.length; i++) {
            rightAcc += (long)nums[i] * cost[i];
            rightCost += cost[i];
        }
        
        Integer[] arr = IntStream.range(0, nums.length).boxed().toArray(Integer[]::new);
        
        Arrays.sort(arr, Comparator.comparingInt(x -> nums[x]));
        
        long ans = rightAcc;
        
        long leftCost = 0, leftAcc = 0;    
        for (int i = 0, j = 0; j < nums.length; i++) {
            ans = Math.min(ans, leftAcc + rightAcc);
            
            while (j < nums.length && nums[arr[j]] <= i) {
                leftCost += cost[arr[j]];
                rightCost -= cost[arr[j]];
                j++;
            }
            
            leftAcc = leftAcc + leftCost;
            rightAcc -= rightCost;
        }
        
        return ans;
    }
    
    
}

方法四: 寻找中位数(赛后补充)

这个需要数学知识，确实差很多。

Java在用流计算值的时候，需要注意溢出的问题。

Java

class Solution {
    
    // 寻找中位点
    public long minCost(int[] nums, int[] cost) {
        
        int n = nums.length;
        Integer[] arr = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(arr, Comparator.comparingInt(a -> nums[a]));
        
        // 寻找中点
        long total = Arrays.stream(cost).mapToLong(Long::valueOf).sum();
        long acc = 0, mid = n - 1;
        
        for (int i = 0; i < n; i++) {
            acc += cost[arr[i]];
            if (acc >= total / 2) {
                mid = nums[arr[i]];
                break;
            }
        }

        
        long ans = 0;
        for (int i = 0; i < nums.length; i++) {
            ans += (long)Math.abs(nums[i] - mid) * cost[i];
        }        
        return ans;
    }
    
    
}

T4. 使数组相似的最少操作次数

6217. 使数组相似的最少操作次数

是个脑筋急转弯吧，但是求解的时候，需要奇偶分组，然后排序，贪心即可。

其实说不出个所以来。

Java

class Solution {
    
    
    long solve(List<Integer> arr, List<Integer> brr) {
        long ans = 0;
        int n = arr.size();
        
        long delta = 0;
        for (int i = 0; i < n; i++) {
            int v1 = arr.get(i);
            int v2 = brr.get(i);
            
            if (v1 > v2) {
                ans += Math.abs(v1 - v2) / 2;
            }
        }    
        
        return ans;
    }
    
    public long makeSimilar(int[] nums, int[] target) {

        // 脑筋急转弯吗？  
        // 先排序
        Arrays.sort(nums);
        Arrays.sort(target);
        
        int n = nums.length;
        
        // 奇偶分组
        List<Integer> xp1 = new ArrayList<>();
        List<Integer> xp2 = new ArrayList<>();
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 1) {
                xp1.add(nums[i]);
            } else {
                xp2.add(nums[i]);
            }
        }
        
        List<Integer> yp1 = new ArrayList<>();
        List<Integer> yp2 = new ArrayList<>();
        for (int i = 0; i < target.length; i++) {
            if (target[i] % 2 == 1) {
                yp1.add(target[i]);
            } else {
                yp2.add(target[i]);
            }
        }
        
        return solve(xp1, yp1) + solve(xp2, yp2);
        
        
    }
    
}

写在最后

珂朵莉MM还是菜菜，感觉lc打周赛的同学越来越强了。