前面的话

第一次参加Leetcode周赛

这次参加了周日上午十点半的第366次周赛。

在平板上打的，还没开code-server，直接用网站的在线编辑器。

开打的时候还在上着C语言理论课，不得不说这个老师还挺开明。

认为自己掌握了可以直接不来上课，让舍友帮忙签到（原话）。

如果来了就别迟到或者早退，此外在课上干什么都可以。

在这样的背景下就可以上课打lc周赛了。

对比一些老师，真的是课越水抓得越严。C语言和高数这两节课老师根本不抓，每次前排都能坐满。

比赛结果

只能做出简单的前两题。

第一题还因为写反一个变量阴沟翻船了。

题目

T1

原题链接

题面

分类求和并作差

给你两个正整数 $n$ 和 $m$ 。

现定义两个整数 $num1$ 和 $num2$ ，如下所示：

$num1$：范围 $[1, n]$ 内所有 无法被 $m$ 整除 的整数之和。

$num2$：范围 $[1, n]$ 内所有 能够被 $m$ 整除 的整数之和。

返回整数 $num1 - num2$。

分析

一眼想到的思路就是把$[1,n]$列出来判断奇偶相加就行了。

虽然这种太有规律的题肯定可以用数学公式推出来，但竞赛毕竟是看用时的，所以直接暴力枚举秒了。

(第一次提交的时候把sum1和sum2对应的含义弄反了，痛吃罚时5min。希望AK杯的时候不要犯这种低级错误了！)

代码

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int differenceOfSums(int n, int m) {
        int num1 = 0, num2 = 0;
        for (int i = 1; i <= n; ++i) {
            if (i % m == 0) num2+= i;
            else num1+=i;
        }
        return num1 - num2;
    }
};

T2

原题链接

题面

你有 $n$ 颗处理器，每颗处理器都有 $4$ 个核心。现有 $n * 4$ 个待执行任务，每个核心只执行一个任务。

给你一个下标从 $0$ 开始的整数数组 $processorTime$ ，表示每颗处理器最早空闲时间。另给你一个下标从 $0$ 开始的整数数组 $tasks$ ，表示执行每个任务所需的时间。返回所有任务都执行完毕需要的最小时间 。

注意：每个核心独立执行任务。

1
2
3
4
5
6
7

输入：processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]
输出：16
解释：
最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器（最早空闲时间 time = 8），下标为 0, 1, 2, 3 的任务分配给第二颗处理器（最早空闲时间 time = 10）。 
第一颗处理器执行完所有任务需要花费的时间 = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16 。
第二颗处理器执行完所有任务需要花费的时间 = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13 。
因此，可以证明执行完所有任务需要花费的最小时间是 16 。

分析

看上去有点复杂呢，什么处理器都出来了。

分析一下样例，很容易能注意到：

要使执行任务最短，要让CPU最早空闲时间大的去匹配任务用时小的，任务用时大的要用CPU最早空闲小的。

那么可以用贪心思路解决了。

先把这两个数组排序。

一个从大到小，一个从小到大。

再每四个任务跟一个处理器匹配。

保存最长任务用时就可以了。

(lambda表达式用在sort自定义比较参数里确实方便。看上去很高级，其实目前我这个水平使用深度来说lambda真的很简单)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int minProcessingTime(vector<int>& processorTime, vector<int>& tasks) {
        sort(processorTime.begin(),processorTime.end());
        sort(tasks.begin(),tasks.end(), [](auto& a, auto& b) {return a>b;});
        int proMax = -1, taMax = -1;
        int cnt = -1;
        for(auto& pt:processorTime) {
            for(int i = 0; i < 4; i++) {
                taMax = max(taMax, pt+tasks[++cnt]);
            }
            proMax = max(proMax, taMax);
        }
        return proMax;
    }
};

最后

这次16min完成比赛（除去罚时应该是11min的呜呜），T3感觉用搜索做，T4又是二进制哈哈。

T4应该要把1都凑在一起，但每个数都统计二进制1个数会不会有点麻烦啊。

希望下次自己能完成更多的题目吧！