一、憤怒的羊駝

題目描述

動物園來了 $C$ 只羊駝，為此動物園需要建造一個有 $N$ 個隔間的棚子，這些隔間分布在一條直線上，坐標是 $x_1,x_2,x_3,...,x_n$。羊駝在隔間的位置分布必須合理，不然羊駝會認為自己處于危險之中，開始互相吐口水來保護自己，那整個動物園將會臭氣熏天！所以為了讓羊駝感到安全，在把它們安置在指定的隔間時，所有羊駝中相鄰兩只的最近距離越大越好。那么，這個最大的最近距離是多少？

輸入描述

第一行，兩個整數 $N,C$。
第二行，$N$ 個整數，表示每個隔間的坐標。

輸出描述

輸出只有一行，即相鄰兩只羊駝最大的最近距離。

樣例1

輸入

5 3
1 2 8 4 9

輸出

3

提示

$2\le C\le N\le 10^5$
$0\le x_i\le 10^9$

參考答案

#include <iostream>
#include <algorithm>
using namespace std;int N, C;
int mid;
int pos[100005];// 按照當前的距離 mid，計算是否能放下 c 只羊駝
bool check(int mid)
{int cnt = 1;  // 記錄放羊駝的數量int prev = pos[1];  // 記錄第一個隔間的位置// 依次遍歷第二到第n個隔間for (int i = 2; i <= N; i++){// 如果下一個隔間到當前隔間的距離大于等于 midif (pos[i]-prev >= mid){cnt++;  // 可以放一只羊駝，記錄數量prev = pos[i];  // 更新當前隔間的位置為下一個隔間}}// 返回當前距離 mid 是否能夠放下 c 只羊駝return (cnt >= C);
}int main()
{// 輸入cin >> N >> C;for (int i = 1; i <= N; i++){cin >> pos[i];}sort(pos+1, pos+N+1);  // 將隔間位置從小到大排序int l = 1;  // 最小距離為1int r = pos[N] - pos[1];  // 最大距離為最后一個隔間位置減去第一個隔間位置int ans = 0;// 二分查找最大的最近距離while (l <= r){mid = (l+r) / 2;if (check(mid)){ans = mid;l = mid+1;}else{r = mid-1;}}// 輸出最近距離cout << ans;return 0;
}

二、偷吃西瓜

題目描述

深藍的天空中掛著一輪金黃的圓月，下面是海邊的沙地，都種著一望無際的碧綠的西瓜…閏土看管著 $N$ 個瓜田，第 $i$ 塊瓜田中有 $a_i$ 個西瓜。今天閏土被父親叫走幫忙了，將在 $H$ 小時后回來。
猹吃西瓜的速度為 $K$（單位：個/小時）。每個小時，猹會選擇一塊瓜田，從中吃掉 $K$ 個西瓜。如果這片瓜田少于 $K$ 個，猹會吃掉這片瓜田所有的西瓜，然后這一小時內不會再吃更多的西瓜。
如果猹想在閏土回來前吃掉所有的西瓜，那么需要計算在 $H$ 小時內吃掉所有西瓜的最小速度 $K$（$K$為整數）。

輸入描述

第一行為兩個整數 $N,H$。
第二行為 $N$ 個整數 $a_i$，第 $i$ 塊瓜田中有 $a_i$ 個西瓜。

輸出描述

一個整數，可以在 $H$ 小時內吃掉所有西瓜的最小速度 $K$。

樣例1

輸入

4 8
3 6 7 11

輸出

4

提示

$1\le N\le 10^6$
$N\le H\le 10^9$
$1\le a_i\le 10^9$

參考答案

#include <iostream>
using namespace std;int N, H;
int ans;
int a[1000005];// 檢查當前速度 mid 是否可以在 H 小時內吃完
bool check(int mid)
{long long t = 0;for (int i = 1; i <= N; i++){t += (a[i]+mid-1)/mid;}return (t <= H);
}int main()
{// 輸入cin >> N >> H;for (int i = 1; i <= N; i++){cin >> a[i];ans = max(ans, a[i]);}// 二分int l = 1, r = ans;while (l <= r){int mid = (l+r) / 2;if (check(mid)){ans = mid;r = mid-1;}else{l = mid+1;}}// 輸出cout << ans;return 0;
}

三、丟沙包

題目描述

A 小時候特別喜歡玩丟沙包游戲，周末休息時，他想找朋友一起玩，并且制定了新的規則，其中有個問題，A 需要幫助。當所有 $n$ 個沙包都丟在一條直線上，現在他想從這些沙包里找出 $c$ 個，使得距離最近的 $2$ 個距離最大，A 想知道，最大可以到多少？

輸入描述

第一行，兩個整數 $n,c$。
第二行，$n$ 個整數，分別為這 $n$ 個沙包坐標，坐標在 $[1,10^9]$ 范圍內。

輸出描述

僅一個整數，為所求答案。

樣例1

輸入

5 3
1 2 3 4 5

輸出

2

提示

$2\le c\le n\le 10^5$

參考答案

#include <iostream>
#include <algorithm>
using namespace std;int n, c;
int pos[100005];// 按照當前的距離 mid 計算是否能丟 c 只沙包
bool check(int mid)
{// 記錄第一個沙包的位置和放沙包的數量int prev = pos[1];int cnt = 1;// 遍歷第二到第n個位置for (int i = 2; i <= n; i++){// 如果下一個位置到當前位置的距離 >= midif (pos[i] - prev >= mid){cnt++; // 下一個位置可以丟一個沙包prev = pos[i]; // 更新當前的位置為下一個位置}}// 返回當前距離 mid 是否能夠丟 c 個沙包return (cnt >= c);
}int main()
{// 輸入cin >> n >> c;for (int i = 1; i <= n; i++){cin >> pos[i];}// 二分sort(pos+1, pos+n+1);int mid, ans = 0;int l = 1, r = pos[n]-pos[1];while (l <= r){mid = (l+r) / 2;if (check(mid)){ans = mid; // 更新答案l = mid+1; // 搜索更大的距離}else{r = mid-1; // 減小距離}}// 輸出cout << ans;return 0;
}

四、木材加工

題目描述

木材廠有 $n$ 根原木，現在想把這些木頭切割成 $k$ 段長度均為 $l$ 的小段木頭（木頭有可能有剩余）。并且，我們希望得到的小段木頭越長越好，請求出 $l$ 的最大值。
木頭長度的單位是 $cm$，原木的長度都是正整數，我們要求切割得到的小段木頭的長度也是正整數。
例如有兩根原木長度分別為 $11$ 和 $21$，要求切割成等長的 $6$ 段，很明顯能切割出來的小段木頭長度最長為 $5$。

輸入描述

輸入文件名為 wood.in。
第一行是兩個正整數 $n,k$，分別表示原木的數量，需要得到的小段的數量。
接下來 $n$ 行，每行一個正整數 $L_i$，表示一根原木的長度。

輸出描述

輸出文件名為 wood.out。
僅一行，即 $l$ 的最大值。
如果連 $1cm$ 長的小段都切不出來（好吧，有億一個樣例是這樣的），輸出 $0$。

樣例1

輸入

3 7
232
124
456

輸出

114

提示

對于 $100\%$ 的測試數據，$1\le n\le 10^5$，$1\le k\le 10^8$，$1\le L_i\le 10^8$。

參考答案

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;int n, k;
int len[100005];// 判斷當前長度 mid 能切段數是否滿足要求段數 m
bool check(int mid)
{// 記錄切割得到的小段數量int cnt = 0;for (int i = 1; i <= n; i++){cnt += len[i]/mid;}// 判斷是否可以切出return (cnt >= k);
}int main()
{freopen("wood.in", "r", stdin);freopen("wood.out", "w", stdout);// 輸入cin >> n >> k;for (int i = 1; i <= n; i++){cin >> len[i];}// 二分sort(len+1, len+n+1);int mid, ans;int l = 1, r = len[n];while (l <= r){mid = (l+r) / 2;if (check(mid)){ans = mid;l = mid+1; // 繼續搜索更大的 l}else{r = mid-1; // 減小 l}}// 輸出cout << ans;fclose(stdin);fclose(stdout);return 0;
}

五、路標設置

題目描述

B 市和 T 市之間有一條長長的高速公路，這條公路的某些地方設有路標，但是大家都感覺路標設得太少了，相鄰兩個路標之間往往隔著相當長的一段距離。為了便于研究這個問題，我們把公路上相鄰路標的最大距離定義為該公路的"空曠指數"。現在政府決定在公路上增設一些路標，使得公路的"空曠指數"最小。他們請求你設計一個程序計算能達到的最小值是多少。請注意，公路的起點和終點保證已設有路標，公路的長度為整數，并且原有路標和新設路標都必須距起點整數個單位距離。

輸入描述

第 $1$ 行包括三個數 $L,N,K$，分別表示公路的長度，原有路標的數量，以及最多可增設的路標數量。
第 $2$ 行包括遞增排列的 $N$ 個整數，分別表示原有的 $N$ 個路標的位置。路標的位置用距起點的距離表示，且一定位于區間 $[0,L]$ 內。

輸出描述

輸出 $1$ 行，包含一個整數，表示增設路標后能達到的最小"空曠指數"值。

樣例1

輸入

101 2 1
0 101

輸出

51

提示

公路原來只在起點和終點處有兩個路標，現在允許新增一個路標，應該把新路標設在距起點 $50$ 或 $51$ 個單位距離處，這樣能達到最小的空曠指數 $51$。
$2\le N\le 10^5$，$0\le K\le 10^5$，$0<L\le 10^7$

參考答案

#include <iostream>
using namespace std;int ans;
int maxn;
int l, n, k;
int a[100005];int check(int mid)
{int cnt = 0;for (int i = 2; i <= n; i++){int tmp = a[i]-a[i-1];while (tmp > mid){tmp -= mid;cnt++;}}return (cnt <= k);
}int main()
{// 輸入cin >> l >> n >> k;for (int i = 1; i <= n; i++){cin >> a[i];maxn = max(maxn, a[i]-a[i-1]);}// 二分int mid;int l = 1, r = maxn;while (l <= r){mid = (l+r) / 2;if (check(mid)){ans = mid;r = mid-1;}else{l = mid+1;}}cout << ans;return 0;
}