首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#13013

坐标选点 题目描述 修建了一条长度为 m 公里的铁路,起点和终点已经建有火车站。铁路沿线有 n 座城市(城市不位于起点或终点),第 i 座城市到铁路起点的距离为…

坐标选点

题目描述

修建了一条长度为 m 公里的铁路,起点和终点已经建有火车站。铁路沿线有 n 座城市(城市不位于起点或终点),第 i 座城市到铁路起点的距离为 ai 公里。

现在计划在这 n 座城市中选择 c 座修建火车站,使得所有火车站(包括起点和终点的火车站)之间的最小相邻距离尽可能大。请你计算这个最小相邻距离的最大可能值。

输入

第一行包含三个正整数n、c、m,分别表示城市数量、计划修建的火车站数量以及铁路总长度。

第二行包含n个正整数a1,a2,...,an,表示每座城市到铁路起点的距离。

输出

输出一个整数,表示最小相邻距离的最大可能值。

数据范围

1≤c≤n≤10^6,1≤ai<m≤10^9,输入中的所有数值均为整数。

输入样例1

5 3 10
1 2 8 4 9

输出样例1

2
未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; int n, c, m, a[1000000] ; bool check(int minDist) {     int count = 0;          // 已经选择的中间火车站数量     int lastPos = 0;        // 上一个火车站的位置(起点)     for (int i = 0; i &lt; n; i++) {         if (a[i] - lastPos &gt;= minDist) {             count++;             lastPos = a[i];             if (count &gt;= c) break; // 已经选够         }     }     // 检查最后一个火车站到终点的距离是否满足     if (count &gt;= c &amp;&amp; (m - lastPos) &gt;= minDist) {         return true;     }     return false; } int main() {     cin &gt;&gt; n &gt;&gt; c &gt;&gt; m;     for (int i = 0; i &lt; n; i++) {         cin &gt;&gt; a[i];     }     sort(a, a+n);     int low = 1, high = m, ans = 0;     while (low &lt;= high) {         int mid = (low + high) / 2;         if (check(mid)) {             ans = mid;             low = mid + 1; // 尝试更大的距离         } else {             high = mid - 1;         }     }     cout &lt;&lt; ans &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。