天天看點

Luogu P3853 路标設定

這大概是我第一次發

Luogu P3853 路标設定

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

Luogu P3853 路标設定

題面

&

\&

&

Luogu P3853 路标設定

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

如果你要拿

Luogu P3853 路标設定

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

我的老師說過:求最小值的最大值(最大值的最小值),跑不了二分答案。

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

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

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

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

Luogu P3853 路标設定

(圖畫的很醜,拿滑鼠畫的我盡力了)

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

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 P3853 路标設定

拓展

Luogu P2678 跳石頭

Luogu P3853 路标設定

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

// 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;
}      

題外話

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

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

Luogu P3853 路标設定

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