题目描述
给你一个长度为n的严格递增的数组,对于数组中的任意一个数字i你至多可执行以下操作一次:
·将i变成 i + 1 或 i - 1。
问你是否能通过上述操作将所给数组变成一个连续的递增数组。
思路
容易想到,执行多次操作后a数组里的坑位最多能被填上两个
C++ 代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef pair<int, int> pii;
std::vector<int> tt;
void solve() {
i64 sum = 0;
int n;
cin >> n;
vector<int> v(n);
for (auto &i : v) cin >> i;
if (n == 1) {
cout << "YES\n";
return;
}
for (int i = 1; i < n; i++) {
sum += v[i] - v[i - 1];
}
i64 tmp = n + 1;
if (sum <= tmp) cout << "YES\n";
else cout << "NO\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
tt.push_back(0);
int tmp = 1;
while (tt.back() < 40) {
int t = tt.back() + tmp;
tmp ++;
tt.push_back(t);
}
int t;
for (cin >> t; t; t --) solve();
return 0;
}