2023 滴滴笔试题 0915
笔试时间:2023年9月15日 秋招
第一题
题目:照明灯安装
你负责在一条笔直的道路上安装一些照明灯。但是道路上并不是任意位置都适合安装照明灯,具体地,假设将道路看作一条起点坐标为0,终点坐标为M的线段,那么只有在x1,x2,...,xn这n个坐标可以安装照明灯,且每个坐标上最多只能安装一个照明灯。现在你要在道路上安装k个照明灯,为了使照明灯能够尽量覆盖道路,你需要使距离最近的两个照明灯尽量远。请问这个最近距离最大可以是多少?
输入描述
第一行是两个整数n、k,分别表示可以安装照明灯的位置数和需要安装的照明灯数量。
接下来一行n个整数x1,x2,...,xn表示可以安装照明灯的坐标。保证x1<x2<...<xn。
1<=k<=n<=100000,1<xi<1000000
输出描述
一行,一个整数,表示最近距离的最大值.
样例输入
5 3
1 3 4 7 9
样例输出
3
提示
分别放在1、4、7的位置(放在1、4、9也可以)
能够证明3是最小的最大距离。
参考题解
二分
C++:[此代码未进行大量数据的测试,仅供参考]
#include <iostream> #include <vector> #include <algorithm> using namespace std; bool check(const vector<int>& a, int k, int dis) { int cnt = 1; int last = a[0]; for (int i = 1; i < a.size() && cnt < k; i++) { if (a[i] >= last + dis) { cnt++; last = a[i]; } } return cnt >= k; } int main() { ios::sync_with_stdio(false); int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; int l = 0, r = 1e9, ans = -1; while (l <= r) { int mid = (l + r) >> 1; if (check(a, k, mid)) { ans = mid; l = mid + 1; } else { r = mid - 1; } } cout << ans << '\n'; return 0; }
Java:[此代码未进行大量数据的测试,仅供参考]
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = scanner.nextInt(); } int l = 0; int r = 1000000000; int ans = -1; while (l <= r) { int mid = (l + r) / 2; if (check
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
2023 秋招笔试题汇总解析 文章被收录于专栏
2023秋招各大笔试题汇总,c++,java,python多种语言分析,解答。