- Bài 3 + 4 : link dưới thcs-vp-2021-4118

Thuật toán

Bài 4 trên trang ucode test có vẻ hơi lỗi nên mình chưa làm nhé.

Ta có thể sử dụng thuật toán tìm kiếm nhị phân cho bài 3 này.

Ta thấy, nếu ta có thể sử dụng $\leq k$ bài tập để độ khó các bài là $x$ thì ta cũng hoàn toàn có thể tạo ra độ khó $x+1$ với $\leq k$ bài tập.

Ngược lại, nếu ta không thể sử dụng $\leq k$ bài tập để độ khó các bài là $x$ thì ta cũng không thể tạo ra độ khó $x-1$ với $\leq k$ bài tập.

Như vậy ta có thể chặt nhị phân theo độ khó bài nhỏ nhất, và bài toán lúc này trở thành kiểm tra xem với độ khó $x$ có thể sử dụng $\leq k$ bài tập để tạo thành không.

Để làm được việc này, ta sẽ sử dụng thuật toán tham lam để tìm số bài tập tối thiểu cần dùng để đạt độ khó $x$. Giá trị đó bằng

$$v = \sum_{i=2}^{n} \left\lceil \dfrac{m_i - m_{i-1}}{x} \right\rceil$$

Ta chỉ cần so sánh $v$ với $k$ là sẽ tìm được đáp án.

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;

int n,k,m[maxn],maxdis,l,r,mid;

bool check(int x){
    // Co the tao ra ban ke hoach do kho x
    int v=0;
    for(int i=2;i<=n;i++){
        v += ceil(1.0*(m[i]-m[i-1])/x) - 1;
    }
    return v <= k;
}

int main(){
    cin >> n >> k;
    maxdis=0; // Do kho bai tap ban dau
    for(int i=1;i<=n;i++) {
        cin >> m[i];
        if(i > 1) maxdis = max(maxdis, m[i] - m[i-1]);
    }
    if(maxdis == 0){
        cout << 0;
        return 0;
    }
    l = 1; r = maxdis;
    while(l <= r){
        mid = (l+r)/2;
        if(check(mid)) r = mid-1;
        else l = mid+1;
    }
    cout << l;
}