Editorial for Liên tiếp

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: hhc

Đầu tiên, ta ~sort~ dãy lại, sau đó tạo ra một dãy mới chỉ gồm các giá trị không trùng lặp và giữ nguyên thứ tự ban đầu.

Coi ~a~ là dãy mới của ta sau khi thực hiện các thao tác trên.

Bây giờ, với mỗi giá trị ~a_i~, ta sẽ giả sử xem nếu như dãy liên tiếp của ta bắt đầu từ giá trị ~a_i~ tới ~a_i+n-1~, ta sẽ phải thay đổi giá trị của bao nhiêu số.

Để làm được điều này, ta sẽ tìm xem có bao nhiêu số trong dãy ~a~ có giá trị trong khoảng ~[a_i,a_i+n-1]~, do dãy ~a~ đã được sắp xếp và không có giá trị trùng lặp, ta có thể đếm bằng cách tìm kiếm nhị phân.

Giả sử có ~x~ số như vậy, do ta sẽ không cần thay đổi những giá trị xuất hiện trong đoạn ~[a_i,a_i+n-1]~ nữa, vậy nên kết quả sẽ là ~n-x~.

Ta sẽ thực hiện thao tác trên với mỗi ~a_i~ và chọn ra kết quả tốt nhất.

Code:

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

#define pi pair<int, int>
#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
#define all(x) x.begin(), x.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
#define int long long
#define setinf(d) memset(d, inf32, sizeof d)
#define setneg(d) memset(d, -1, sizeof d)
#define set0(d) memset(d, 0, sizeof d)
#define Log2(x) 63 - __builtin_clzll(x)
#define oo 2e18
#define mod 1000000007
#define FILENAME "f"

vector<int> a;
int n;

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> n;
    a = vector<int>(n);

    for(int &d : a) cin >> d;

    sort(all(a));
     Unique(a);

    int ans = 0;

    for(int &d : a){
        ans = max(ans, (int)(upper_bound(all(a), d + n - 1) - lower_bound(all(a), d)));
    }

    cout << n - ans;
}