Hướng dẫn giải của Liên tiếp

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: 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;
}