8.10 贝壳真题

第一题计算绝对值

这题的数据范围较大，应该用 long long

#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<long long> arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    // 记录差值最小的两个数的第一个数的下标
    int res = 0;
    long long iMin = abs(arr[0] - arr[1]);
    for(int i=0; i<n-1; i++){
        long long cur = abs(arr[i] -  arr[i+1]);
        // 当前差值较小，更新最小差值以及下标
        if(iMin > cur){
            iMin = cur;
            res = i;
        }
    }
    cout << arr[res] << ' ' << arr[res+1] << endl;
    return 0;
}

第二题月光宝盒的密码

最长严格上升子序列，无脑暴力 N^2 能过 82，通过二分法来计算 100

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0; i<n; i++)
        cin >> arr[i];
    int res = 0;
    vector<int> dp;
    dp.push_back(arr[0]);
    for(int i=1; i<n; i++){
        // 当前元素，大于上升序列数组中的最大值，直接放到最后
        if(arr[i] > dp.back()) dp.push_back(arr[i]);
        else {
            // 找到刚好大于当前数在上升序列数组中的下标
            auto it = upper_bound(dp.begin(), dp.end(), arr[i]);
            // 因为是严格上升，需要判断一下，前面的数是否等于现在的数
            if(it == dp.begin() || *(it-1) != arr[i]){
                *it = arr[i];
            }
        }
    }
    cout << dp.size() << endl;
    return 0;
}

第三题检查卫生

涉及到连续的题目通常需要部分和思路来计算

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> arr(n+1, 0);
    // 在赋值的过程中，完成部分和的计算
    for(int i=1; i<=n; i++)
        cin >> arr[i], arr[i] += arr[i-1];
    // 所得分数比较大，用 long long 存放
    long long res = 0;
    // 记录老师们的打分区间，通过部分和的思路，计算出，重叠区域的最大值
    vector<int> brr(n+1, 0);
    for(int i=0; i<m; i++){
        int st, end;
        cin >> st >> end;
        // 如果没有房间会重新打扫的话，应该获得的分数
        res += arr[end] - arr[st-1];
        brr[st-1]++;
        brr[end]--;
    }
    // 计算老师们的打分区间，并算出哪个房间被老师关顾最多，打扫那个房间即可
    int iMax = 0;
    for(int i=1; i<=n; i++)
        brr[i] += brr[i-1], iMax = max(iMax, brr[i]);

    cout << res + iMax << endl;

    return 0;
}

第四题特殊的测试

不知道为什么，我的代码时间复杂度是 O(N)
就是只过 82%, 改了好多版本，最后优化成下面的样子

#include <iostream>
#include <vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> arr(n);
    vector<int> dp(n, 0);
    for(int i=0; i<n; i++)
        cin >> arr[i];

    int pre = arr[0];
    for(int i=1; i<n; i++){
        // 把数组从 0 到 i  加成递增需要的数量
        dp[i] = dp[i-1] + max(0, pre - arr[i] + 1);
        pre = max(pre + 1, arr[i]);
    }

    int res = dp.back(), cur = 0;
    pre = arr.back();
    for(int i=n-2; i>=0; i--){
        // 重复加 的部分
        int repeat = min(dp[i] - (i==0 ? 0 : dp[i-1]) , max(0, pre - arr[i] + 1));

        // 把数组从 i 到 n-1 加成递减需要的数量
        cur += max(0, pre - arr[i] + 1);
        pre = max(pre + 1, arr[i]);
        // dp[i] + cur - repeat  这个值为把第 i 个元素变成最大的元素，往左递减，往右递减，需要花费的最小代价
        // 算出每一个情况，取最小
        res = min(dp[i] + cur - repeat, res);
    }
    cout << res << endl;

    return 0;
}

图片说明