Biweekly Contest 11

Posted on | In , | |
Words count in article: 586 | Reading time ≈ 2

等差数列中缺失的数字

1
2
3
4
5
6
int missingNumber(vector<int>& arr) {
    // 数组求和
    int sum = accumulate(arr.begin(), arr.end(), 0);
    // 公式求和 - 数组求和
    return (arr.size() + 1) * (arr.front() + arr.back()) / 2 - sum;
}

安排会议日程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
    // 区间排序
    sort(slots1.begin(), slots1.end());
    sort(slots2.begin(), slots2.end());
    int i = 0, j = 0, n1 = slots1.size(), n2 = slots2.size();
    while (i < n1 && j < n2) {
        // 当前对比区间为 第一个人的第 i 个区间，第二个人的第 j 的区间
        // 区间开始为两个人开始的最晚值，区间结束为两个人结束的最早值
        int st = max(slots1[i][0], slots2[j][0]), en = min(slots1[i][1], slots2[j][1]);
        // 重叠区间够会议时间
        if (en >= st + duration) return {st, st+duration};
        // 谁的结束时间比较早，向后移动一位
        if(slots1[i][1] > slots2[j][1]) j++;
        else i++;
    }
    return {};
}

抛掷硬币

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
double probabilityOfHeads(vector<double>& prob, int target) {
    int len = prob.size();
    // dp[i][j] 代表    掷了 i 个骰子，正面向上的个数为 j
    vector<vector<double>> dp(len+1, vector<double>(target+1, 0));
    // 初始，掷出 0 的概率为 1
    dp[0][0] = 1.0;s
    for (int i = 1; i <= len; i++) {
        for (int j = min(i, target); j > 0; j--)
            // 递推公式， dp[i][j] = dp[i-1][j] * 当前骰子反面在上的概率 + dp[i-1][j-1] * 当前骰子正面在上的概率
            dp[i][j] = dp[i-1][j] * (1 - prob[i-1]) + dp[i-1][j-1] * prob[i-1];
        // 单独对 0 的情况进行更新
        dp[i][0] = dp[i-1][0] * (1 - prob[i-1]);
    }       
    
    return dp[len][target];
}

分享巧克力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maximizeSweetness(vector<int>& a, int K) {
    // 二分的边界 left = *min_element(a.begin(), a.end());
    // right = accumulate(a.begin(), a.end(), 0) / ( K + 1) + 1;
    int left = 0, right = 1e9 + 7, len = a.size();
    while (left < right) {
        // mid 向上取整，在一般的二分里 left = mid + 1, right = mid
        // 在当前这个二分中 left = mid, right = mid - 1  所以向上取整时，可以防止无限循环
        int mid = (left + right + 1) >> 1, cnt = 0, tem = 0;
        // 计算当前 mid 是否满足
        for (int i = 0; i < len; i++) {
            if (tem + a[i] >= mid) cnt++, tem = 0;
            else tem += a[i];
        }
        // cnt >= K + 1 时  代表当前可以这样拆分
        if (cnt >= K + 1) left = mid;
        else right = mid - 1;
    }
    return left;
}
Donate? comment?