Bilibili暑期实习笔试
两道题。一道思维，一道二分。（第一个是力扣那种写函数的题）
- 给一个数组，将其划分成
个子数组（不需要连续）。问每个子数组极差的和最大是多少。
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;
}
- 一共有
个苹果，
个小孩，这些小孩排成一排，小明是第
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;
}
米哈游公司福利 3760人发布
查看7道真题和解析
投递饿了么等公司8个岗位 >