Bilibili暑期实习笔试

两道题。一道思维，一道二分。（第一个是力扣那种写函数的题）

1. 给一个数组，将其划分成个子数组（不需要连续）。问每个子数组极差的和最大是多少。

Code:

int solution(vector<int> nums, int k) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    int res = 0;
    for (int i = 1; i <= min(k, n - k); ++i) res += nums[n - i] - nums[i - 1];
    return res;
}

2. 一共有个苹果，个小孩，这些小孩排成一排，小明是第个小孩（下标从1开始）。给每个人分配苹果，每个小孩至少分一个苹果，相邻的小孩分配的苹果数量差不能超过1。问小明最多能分到多少个苹果。

Code:

#include <bits/stdc++.h>

using namespace std;

#define LL long long

bool ok(LL x, LL k, LL n, LL m) {
    LL mx = (x + 1 + x + n - k) * (n - k) / 2 + x + (x + 1 + x + k - 1) * (k - 1) / 2;
    if (mx < m) return false;
    LL mi = x;
    if (x - (n - k) >= 1) mi += (x - 1 + x - (n - k)) * (n - k) / 2;
    else mi += (x - 1 + 1) * (x - 1) / 2 + n - k - (x - 1);
    if (x - (k - 1) >= 1) mi += (x - 1 + x - (k - 1)) * (k - 1) / 2;
    else mi += (x - 1 + 1) * (x - 1) / 2 + k - 1 - (x - 1);
    return mi <= m;
}

int solution(int n, int m, int k) {
    if (n == 1) return m;
    LL l = 1, r = m, f = -1;
    while (l <= r) {
        LL mid = (l + r) >> 1;
        if (ok(mid, k, n, m)) {
            f = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return f;
}
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    cout << solution(n, m, k) << endl;
    return 0;
}