描述

每年奶牛們都要舉辦各種特殊版本的跳房子比賽，包括在河里從一個(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í)間限制：1s

空間限制：128MB

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int maxn = 50000 + 10 ; int dis[maxn]; int main() { // freopen("stone.in","r",stdin); // freopen("stone.out","w",stdout);int L,n,m;cin>>L>>n>>m;for(int i=1;i<=n;i++)scanf("%d",&dis[i]);int l=1,r=L;sort(dis+1,dis+n+1);while(l<r){int i,mid = ( l + r + 1 ) >> 1,pos(0),temp(0);for(i=1;i<=n;i++){if(dis[i]+mid>L) break;if(dis[i]-pos<mid) temp++;else pos = dis[i];}temp+=n-i+1;if(temp<=m) l=mid;else r=mid-1;}cout<<l<<endl;return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/hfang/p/11239892.html

總結(jié)

以上是生活随笔為你收集整理的河中跳房子（noiopenjudge,noip2015）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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