Luogu P3853 路标設定

這大概是我第一次發

難題的題解吧……這道題我整了好幾天，才過。

題面

&

\&

&

如果單純地思考怎麼拿部分分，那這個題并不難，暴力模拟一遍就行了，小樣例能過。

如果你要拿

，那你就不能枚舉了，需要二分降低時間複雜度。

我的老師說過：求最小值的最大值（最大值的最小值），跑不了二分答案。

因為起點和終點都有路标，是以我們可以确定出“空曠值”的範圍啦（即下限為 ， 上限為 ）。我們在這期間開始二分答案每一個“空曠值”。

思考一下，二分答案的判斷函數怎麼寫呢？

我們可以從第一個路标枚舉到最後一個路标，取兩個路标的距離差。如果這個距離差大于，那麼我們就可以增加一個路标了。

為了進一步降低時間複雜度，我們可以使用國小數學來解決一下。我們可以知道：

（圖畫的很醜，拿滑鼠畫的我盡力了）

考慮一種特殊情況，如果距離差剛好整除，那麼需要減去一。

我們用一個計數器記錄每一個距離差之間放的路标數量。我們可以根據和最多放的路标數量作比較，如果傳回真，反之傳回假。

再說二分模闆，我們可以根據函數的傳回值來對應和的變化。如果傳回值為真，說明空曠值還可以進一步縮小；反之表示空曠值過小。

是以如果傳回真，我們需要往左看；傳回假，我們需要向右看。

由于最後是求最小值，是以需要輸出左邊界。

完整程式如下：

// Author:PanDaoxi
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e5 + 1;
int k, n, m, l, r, mid, a[INF];

bool check(int t){
  int cnt = 0,
    now = 0;
  for(int i=1; i<=n; i++){
    /*
            取兩個路标之差x，cnt+=x/t
            特判如果x%t為0，那麼cnt--
    */
      now = a[i] - now;
    if(now > t) cnt += now/t - (now%t == 0);
    now = a[i];
  }
  if(cnt <= m) return true;
  else return false;
}

int main(){
  ios :: sync_with_stdio(false);

  cin >> k >> n >> m;
  for(int i=1; i<=n; i++){
    cin >> a[i];
  }
  l = 0, r = k;

  while(l <= r){
    mid = (l+r) / 2;
    if(check(mid)){
      r = mid - 1;
    }
    else{
      l = mid + 1;
    }
  }
  cout << l;

  return 0;
}      

拓展

Luogu P2678 跳石頭

類比于《路标設定》的思想，剛才的那道題是枚舉空曠指數，這個題是枚舉跳躍距離。思考一下，得到以下程式：

// Author:PanDaoxi
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int INF = 5e4 + 1;
int k, m, n, l, r, mid, a[INF];

bool check(int t){
  int cnt = 0,
    now = 0;
  for(int i=1; i<=n; i++){
    if(a[i] - now >= t) now = a[i];
    else cnt++;
  }
  if(k - now < t){
    cnt++;
  }
  if(cnt <= m) return true;
  else return false;
}

signed main(){
  ios :: sync_with_stdio(false);
  
  cin >> k >> n >> m;
  l = 1, r = k;
  for(int i=1; i<=n; i++){
    cin >> a[i];
  }

  while(l <= r){
    mid = (l+r) / 2;
    if(check(mid)){
      l = mid + 1;
    }
    else{
        r = mid - 1;
    }
  }
  cout << r;
  
  return 0;
}      

題外話

預祝全天下們程式員節快樂！

我去年來的洛谷，到今天快一年了。

一年前我還啥也不是，現在已經可以開始挑戰難題了（部分是跟着老師做的）