Hướng dẫn giải của Dãy số đẹ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 làm lời giải.
Nộp code mẫu trước khi tự giải được bài tập là một hành vi có thể bị ban.
Tác giả:
Ta đi tìm dãy số đẹp dài nhất. Tức tìm dãy số ~b_1, b_2, ..., b_k~ thoả mãn ~b_{i+1} \ge 2*b_i - b_1~, với ~k~ lớn nhất có thể.
Nhận xét
Với điều kiện ~b_{i+1} - b_i \ge b_i - b_1~ ~(\forall 2 \le i < k)~, thì ta thấy khoảng cách giữa ~b_i~ với ~b_1~ sẽ tăng lên ít nhất gấp đôi theo thứ tự ~i~ tăng dần. Mà giới hạn của các phần tử là ~10^9~, nên dãy sẽ có độ dài tối đa là ~log(10^9)~, tức là khoảng ~30~.
Vì vậy ta nghĩ đến việc: với mỗi vị trí ~i~ trên dãy ~a~, ta tìm dãy con đẹp dài nhất bắt đầu từ ~a_i~. Ta tiến hành chặt nhị phân tìm ~a_j~ nhỏ nhất thoả mãn vị trí tiếp theo (có thể dùng lower_bound).
Độ phức tạp
~O(n.logn.log(a_i))~
Code tham khảo
// Created by BJMinhNhut
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define MASK(i) (1ll<<(i))
#define BIT(t, i) (((t)>>(i))&1)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef pair<int, int> ii;
/***Common Functions***/
template <class T>
bool minimize(T &a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
bool maximize(T &a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/***End of Template***/
int n;
const int N = 2e5+5;
int a[N];
void Input() {
cin >> n;
FOR(i, 1, n) cin >> a[i];
}
void Solve() {
int res = 0;
FOR(i, 1, n) {
if (i > 1 && a[i] == a[i-1]) continue;
int cnt = 2;
int cur = i+1;
while (1) {
int j = lower_bound(a+1+cur, a+1+n, 2*a[cur]-a[i]) - a;
if (j > n) break;
cur = j;
cnt++;
}
maximize(res, cnt);
}
cout << n-res << '\n';
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
while (t--)
Input(), Solve();
return 0;
}
Bình luận