用于個(gè)人學(xué)習(xí)記錄
一、題目描述
二、方法介紹?
? 二分查找——在有序數(shù)組中折半查找所需值（默認(rèn)數(shù)組升序）
代碼實(shí)現(xiàn)
重慶分公司
重慶分公司
#includeint main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };//數(shù)組需為有序數(shù)組
int k = 7;//k為所需值
int sz = sizeof(arr) / sizeof(arr[0]);//數(shù)組總大小/每個(gè)數(shù)的大小=數(shù)的個(gè)數(shù)
int left = 0;
int right = sz - 1;//想知道right的值必須先知道數(shù)組中數(shù)的個(gè)數(shù)
while (left<= right)//當(dāng)left >right則表明已沒有可繼續(xù)查找的區(qū)間
{//通過比較區(qū)間中間數(shù)與k的大小一步步縮短區(qū)間最終找到k
//int mid = (right + left) / 2;//這種方法求mid有弊端，如果left + right超出int的范圍則會(huì)影響mid的值
int mid = left + (right - left) / 2;
if (arr[mid] >k) {
right = mid - 1;//舍棄右側(cè)區(qū)間
}
else if (arr[mid]< k) {
left = mid + 1;//舍棄左側(cè)區(qū)間
}
else if (arr[mid] == k){
printf("下標(biāo)為：%d", mid);//此時(shí)返回的為數(shù)在數(shù)組中的下標(biāo)
break;//找到所需值時(shí)即可終止
}
}
if (left >right)
{
printf("false");//代表未能在數(shù)組中找到所需值
}
return 0;
} 三、題解
最短跳躍距離的大值（說實(shí)話我一開始半天沒讀懂，語文不好真的會(huì)對(duì)題目這種說法疑惑，不過可能只有我沒看懂）
以題目樣例為例
? 一開始的石頭分別位于2 11 14 17 21
? 則相鄰兩塊石頭的距離分別為 2，9，3，3，4，4(包括第一塊與起始位置的距離，最后一塊與終點(diǎn)的距離)此時(shí)最短跳躍距離為2
? 移去距離為2和14的兩塊石頭后，相鄰兩塊石頭間距離分別為11，6，4，4則最短跳躍距離為4
假設(shè)移走的為距離為2和17的，那么相鄰兩塊石頭間距離分別為11，3，7，4則最短跳躍距離為3，小于4。同樣可以假設(shè)移走另外兩塊石頭，會(huì)發(fā)現(xiàn)得出的最短跳躍距離均小于4，所以4為最短跳躍距離的大值。
拋開一切其他條件時(shí)最短跳躍距離大可為起始點(diǎn)與終點(diǎn)距離(總距離)的一半，所以可將總距離視為一個(gè)升序數(shù)組，從一到總距離均為可能的解的值，用二分法查找符合條件的大的解能為多少，判斷條件即為要使最短跳躍距離為這個(gè)值，需要移走的石頭數(shù)量是否符合條件。
代碼實(shí)現(xiàn)
#define _CRT_SECURE_NO_WARNINGS
#includeint L = 0, N = 0, M = 0;//起點(diǎn)和終點(diǎn)的距離(總距離)，巖石數(shù)量,移走的巖石的數(shù)量
int n[50002] = { 0 };//記錄每塊石頭與起點(diǎn)的距離
int judge(int x) {//判斷此時(shí)的解是否符合要求(搬走的石頭的數(shù)量不超過M)
int count = 0;//記錄在最短距離為x的情況下需要搬走的石頭的數(shù)量
int now = 0, to = 1;//現(xiàn)在的位置和要去的位置
while (to<= N + 1) {//最后一塊石頭跳到終點(diǎn)的距離也要判斷
if (n[to] - n[now]< x) {//此時(shí)這兩塊石頭之間的距離沒有達(dá)到假設(shè)的最小距離
count++;//搬走這塊石頭使此時(shí)所在石頭與下一塊石頭之間的距離增大
}
else {//此時(shí)所在石頭與下一塊石頭間的距離符合假設(shè)的值不需要搬走石頭，直接跳過去，所以更新此時(shí)所在的位置
now = to;
}
to++;
}
if (count >M)
return 0;
else
return 1;
}
//主函數(shù)
int main()
{
scanf("%d %d %d", &L, &N, &M);
n[0] = 0, n[N + 1] = L;//記錄起始點(diǎn)和終點(diǎn)
for (int i = 1; i<= N; i++) {
scanf("%d", &n[i]);
}
int left = 0, right = L;//從大的可能開始逐個(gè)排除(一步登天)
int mlen = 0;//記錄結(jié)果
while (left<= right) {
int mid = (left + right) / 2;
if (judge(mid) == 1) {//如果此時(shí)的mid符合要求(一般都不會(huì)是大值<是大好像也不影響>,所以要判斷是否有更大的可行值)
mlen = mid;//先記錄一下此時(shí)的答案
left = mid + 1;//判斷是否有更大的可行值
}
else {//最小距離的大值不能達(dá)到mid,減小這個(gè)值
right = mid - 1;
}
}
printf("%d", mlen);
return 0;
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
