1247：河中跳房子

時(shí)間限制: 1000 ms ??? ??? 內(nèi)存限制: 65536 KB
提交數(shù): 5287 ??? 通過(guò)數(shù): 2522

【題目描述】

每年奶牛們都要舉辦各種特殊版本的跳房子比賽，包括在河里從一個(gè)巖石跳到另一個(gè)巖石。這項(xiàng)激動(dòng)人心的活動(dòng)在一條長(zhǎng)長(zhǎng)的筆直河道中進(jìn)行，在起點(diǎn)和離起點(diǎn)L遠(yuǎn) (1 ≤ L≤ 1,000,000,000) 的終點(diǎn)處均有一個(gè)巖石。在起點(diǎn)和終點(diǎn)之間，有N (0 ≤ N ≤ 50,000) 個(gè)巖石，每個(gè)巖石與起點(diǎn)的距離分別為Di (0 < Di < L)。

在比賽過(guò)程中，奶牛輪流從起點(diǎn)出發(fā)，嘗試到達(dá)終點(diǎn)，每一步只能從一個(gè)巖石跳到另一個(gè)巖石。當(dāng)然，實(shí)力不濟(jì)的奶牛是沒(méi)有辦法完成目標(biāo)的。

農(nóng)夫約翰為他的奶牛們感到自豪并且年年都觀看了這項(xiàng)比賽。但隨著時(shí)間的推移，看著其他農(nóng)夫的膽小奶牛們?cè)谙嗑嗪芙膸r石之間緩慢前行，他感到非常厭煩。他計(jì)劃移走一些巖石，使得從起點(diǎn)到終點(diǎn)的過(guò)程中，最短的跳躍距離最長(zhǎng)。他可以移走除起點(diǎn)和終點(diǎn)外的至多M (0 ≤ M ≤ N) 個(gè)巖石。

請(qǐng)幫助約翰確定移走這些巖石后，最長(zhǎng)可能的最短跳躍距離是多少？

【輸入】

第一行包含三個(gè)整數(shù)L, N, M，相鄰兩個(gè)整數(shù)之間用單個(gè)空格隔開(kāi)。

接下來(lái)N行，每行一個(gè)整數(shù)，表示每個(gè)巖石與起點(diǎn)的距離。巖石按與起點(diǎn)距離從近到遠(yuǎn)給出，且不會(huì)有兩個(gè)巖石出現(xiàn)在同一個(gè)位置。

【輸出】

一個(gè)整數(shù)，最長(zhǎng)可能的最短跳躍距離。

【輸入樣例】

25 5 2 2 11 14 17 21

【輸出樣例】

4

【提示】

在移除位于2和14的兩個(gè)巖石之后，最短跳躍距離為4（從17到21或從21到25）。

【分析】

? ? ? ? 采用二分法，最短距離最大。二分時(shí)，如果中間值可行，繼續(xù)猜后一半，對(duì)于一個(gè)答案m，如果可行，那么相鄰石頭之間的距離都不小于m，也就是如果出現(xiàn)小于m的，那個(gè)石頭必須移走。寫(xiě)一個(gè)函數(shù)判斷當(dāng)前答案需要移走多少塊石頭，如果不超過(guò)k塊，那就可以，否則不行。

? ? ? ? 初始left=0，right=25，distance=12，去掉兩個(gè)石頭，剩四個(gè)區(qū)間，我們的問(wèn)題就是找一個(gè)最大的distance，使得這四段區(qū)間距離都不小于distance。即最短距離最大。

? ? ? ? 如果distance=12，那么在從14向后繼續(xù)找，發(fā)現(xiàn)找不到第二顆石頭，調(diào)整區(qū)間left和right，以此類推，繼續(xù)查找。

【參考代碼】

#include <stdio.h> #define N 50010 int blocks[N]; int check(int n,int distance) {int now=0,cnt=0,i;for(i=1;i<=n+1;i++){if(blocks[i]-blocks[now] >= distance){cnt++;now=i;}}return cnt; } int main() {int i,l,n,m;int left,right,distance,ans;scanf("%d%d%d",&l,&n,&m);for(i=1;i<=n;i++)scanf("%d",&blocks[i]);blocks[n+1]=l;left=0;right=l;while(left<=right){distance=(left+right)/2;if(check(n,distance)>=n-m+1){ans=distance;left=distance+1;}else{right=distance-1;}}printf("%d\n",ans);return 0; }

http://ybt.ssoier.cn:8088/problem_show.php?pid=1247

總結(jié)

以上是生活随笔為你收集整理的信息学奥赛一本通（1247：河中跳房子）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。