把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF1610E AmShZ and G.O.A.T
大意：一个数组，求至少删除几个数能使得新的得到的数组里不存在任何子序列，子序列中大于平均数的数严格大于小于平均数的数。

解：

首先我们很容易发现，任何不符合条件的子序列，它中间至少会有一个长度为3的子序列，不满足条件，而问题就转化为了消除所有长度为3的子序列a,b,c，其中b-a>c-b。
而如果满足条件的序列长度为m，那么显然am-am-1>am+1-am，通过这个传递性，我们可以得到，实际上am-am0>am+1-am。
换句话说这是一个跨度逐渐大的级数，如果从一个固定点开始的话我们可以通过二分来得到一条符合条件的路，但值得注意的是，这个开始的固定点是不确定的。
但是没关系，由于这个转移带来的区间是不断增大的，而且每次至少会增加一倍，而ai的范围是1e9，我们可以得到实际上，每个符合条件的序列中与开始的数不同的数的数量一定<log1e9。因此即使枚举开始点，复杂度也不过是O(nlognlog1e9)。
注意上文中的“与开始的数不同”，当一个序列里所有数都相等时，显然序列是成立的，因为am-am0恒等于0，这个时候序列中数的数量显然很容易就超过了log1e9。不过我们反而可以去利用这个特性——当一个起始点与前一个起始点相同时，我们可以直接跳过当前的起始点，因为它的序列长度必定比前一个少1。
由于转移是从两个数开始的，所以要注意特判n=1的情况。
相当有意思的题目，算是数论范畴内吧。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <queue>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 300005
#define mdl 1000000007
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(int i=0;i<n;i++)a[i]=m;
#define endl '\n'
#define pi 3.141592657
using namespace std;
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}
ll cpow(ll x, ll n) {
	ll ans = 1;
	while (n > 0) {
		if (n & 1) ans = (ans * x) % mdl;
		x = (x * x) % mdl;
		n >>= 1;
	}
	return ans;
}
ll getpos(int p, ll n) {
	return n / cpow(10, p - 1) % 10;
}
ll getwei(ll n) {
	int res = 0;
	while (n) {
		res++;
		n /= 10;
	}
	return res;
}
/*

---------------------------------------------------------------------
5 4
1 3 11 15 32
*/
ll a[maxn];
int main() {
	cfast;
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		inc(i, 0, n) {
			cin >> a[i];
		}
		ll mx = 0;
		if (n == 1) {
			cout << 0 << endl;
			continue;
		}
		inc(i, 0, n-1) {
			if (i > 0 && a[i] == a[i - 1])continue;
			ll st = a[i];
			ll tmp = a[i + 1];
			ll nxt = 2 * a[i + 1] - st;
			int x=i+1;
			ll ans = 2;
			while (x!=n) {
				//cout << " i= "<<i<<" x= " << x << endl;
				ans++;
				tmp = a[x];
				nxt = 2 * tmp - st;
				//cout << " tmp= " << tmp << " nxt= " << nxt << endl;
				x = lower_bound(a + x + 1, a + n, nxt) - a;
			}
			mx = max(mx, ans);
		}
		cout << n - mx+1 << endl;
	}
}
/*
2 3
1 4

*/