[NOIP2015] day2 T1 跳石頭

大家都很強，可與之共勉。

NOIP2015】day2 跳石頭

題目描述

一年一度的“跳石頭”比賽又要開始了！

這項比賽将在一條筆直的河道中進行，河道中分布着一些巨大岩石。組委會已經選擇好了兩塊岩石作為比賽起點和終點。在起點和終點之間，有 N 塊岩石（不含起點和終點的岩石）。在比賽過程中，選手們将從起點出發，每一步跳向相鄰的岩石，直至到達終點。

為了提高比賽難度，組委會計劃移走一些岩石，使得選手們在比賽過程中的最短跳躍距離盡可能長。由于預算限制，組委會至多從起點和終點之間移走 M塊岩石（不能移走起點和終點的岩石）。

輸入格式

輸入檔案第一行包含三個整數 L,N,M,分别表示起點到終點的距離，起點和終點之間的岩石數，以及組委會至多移走的岩石數。保證 L≥1 且 N≥M≥0。

接下來 N行，每行一個整數，第 i 行的整數 Di（0

這是一道玄學題

二分邊界好惡心，不是多一個就是少一個。

玄學題，僅供欣賞。

思路過于low， 就貼上代碼了。

#include "cstdio"
#include "cctype"

template <class T>
inline bool readIn(T &x)  {
    T flag = ;  char ch;
    while(!(isdigit(ch = (char) getchar())) && ch != EOF)  if( ch == '-' )  flag = -;
    if(ch == EOF)  return false;
    for(x = ch - ; isdigit(ch = (char) getchar()); x = (x << ) + (x << ) + ch - );
    x *= flag;
    return true;
}

int n, m, L, l, r, ans, *dis;

inline bool check(int dist)  {
    int cnt = , last = ;
    for(register int i = ; i <= n; ++i)
        if( dis[i] - last < dist )  ++cnt;
        else last = dis[i]; 
    if( cnt > m )  return false;
    return true;
}

int main()  {
    freopen("stone.in", "r", stdin);
    freopen("stone.out", "w", stdout);
    readIn(L);readIn(n);readIn(m);
    dis = new int[(const int) n + ];
    for(register int i = ; i <= n; readIn(dis[i]), ++i);
    dis[++n] = r = L;
    while( l <= r )  {
        int mid = (l + r) >> ;
        check(mid) ? l = mid + , ans = mid: r = mid - ;
    }
    printf("%d\n", ans);
}