B. Shrinking Array
讓我們稱一個數組?b?為?i?美麗?，如果它至少包含兩個元素，并且存在一個位置?|bi?bi+1|≤1?使得?|x|?(其中?x?是 #10# #11# 的絕對值)。
給定一個數組?a?，只要它至少包含兩個元素，你就可以執行以下操作：
- 選擇數組?a?中的兩個相鄰位置?i?和?i+1?。
- 選擇一個整數?x?使得?min(ai,ai+1)≤x≤max(ai,ai+1)?。
- 從數組中移除數字?ai?和?ai+1?，并將數字?x?插入它們的位置。顯然，數組的大小將減少?1?。
計算使數組變得美麗所需的最少操作次數，或者報告不可能。
輸入
第一行包含一個整數?t?(?1≤t≤200?) — 測試用例的數量。
每個測試用例的第一行包含一個整數?n?(?2≤n≤1000?) — 數組?a?的大小。
每個測試用例的第二行包含?n?個整數?a1,a2,…,an?(?1≤ai≤106?) — 數組?a?本身。
輸出
對于每個測試用例，輸出一個整數—使數組?a?變得美麗所需的操作最小數量，或者如果不可能使其變得美麗，則輸出??1?。
示例
輸入
復制
4
4
1 3 3 7
2
6 9
4
3 1 3 7
4
1 3 5 2
輸出
復制
0
-1
1
1
注意
在第一個測試用例中，給定的數組已經是美麗的，因為?|a2?a3|=|3?3|=0?。
在第二個測試用例中，不可能使數組變得美麗，因為應用操作會使其大小減少到少于兩個。
在第三個測試用例中，例如，你可以選擇?a1?和?a2?并將它們替換為數字?2?。得到的數組?[2,3,7]?是美麗的。
在第四個測試用例中，例如，你可以選擇?a2?和?a3?并將它們替換為數字?3?。得到的結果數組?[1,3,2]?是漂亮的。
思路：
其實有點差分的思想在
1.當相鄰的值為-1，0，1時，直接成立
2.當差分的值為全正/全負且不存在在第一種情況，不成立
3.剩余情況是成立的，然后找最小的可能（存在的可能只在差為正負的交界處）；因為時間夠，所有我純暴力，
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t, n, a[1003], b[1003];
int main(){ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin與cout綁定cin >> t;while (t--) {cin >> n;b[0] = 0;bool pan = false;int fu = 0, zhen = 0;for (int i = 1; i <= n; i++) {cin >> a[i];b[i] = a[i] - a[i - 1];if (i != 1 && (b[i] == 1 || b[i] == 0 || b[i] == -1)) {pan = true;}if (i != 1 && !pan && b[i] > 0) {zhen++;}else if (i != 1 && !pan && b[i] < 0) {fu++;}}if (pan) {cout << 0 << endl;}else if (zhen == 0 || fu == 0) {cout << -1 << endl;}else {int MAX_sum = INT_MAX;for (int i = 2; i <= n; i++) {int sum = i;for (int j = i + 1; j <= n; j++) {if (b[i] > 0) {sum += b[j] < 0 ? b[j] : 0;if (sum <= 1) {MAX_sum = MAX_sum < j - i ? MAX_sum : j - i;}}else {sum += b[j] > 0 ? b[j] : 0;if (sum >= -1) {MAX_sum = MAX_sum < j - i ? MAX_sum : j - i;}}}}if (MAX_sum == INT_MAX) {cout << -1 << endl;}else {cout << MAX_sum << endl;}}}return 0;
}
electronjs-v11.2.0升級到新版本electronjs-v37.2.0記錄，node版本記錄，淘寶鏡像配置記錄，升級記錄)
