【CF 125D】 Two progressions 劃分等差數列

翻譯：有一個整數序列a[]，你需要将它劃分成兩個非空序列，滿足兩個序列都是等差數列。"等差數列"定義為相鄰兩項間內插補點相等的非空序列；特别地，長度為1或2的序列也是等差數列，但長度為0的不是(因為必須非空)。"劃分"定義為，将原序列中的所有元素分成兩個序列，滿足每個元素都在恰好一個序列中，且保留其在原序列中的順序。例如[1, 3, 4]和[2, 5]就是[1, 2, 3, 4, 5]的一個劃分，[1, 2, 3]和[4, 5]也是，但[1, 2]和[3, 4]不是(不全)，[2, 1]和[3, 4, 5]也不是(順序不對)。

輸入格式：第一行一個正整數n，第二行n( 2 ≤ n ≤ 30000)個用空格分隔的整數，表示序列a(  - 108 ≤ ai ≤ 108)，且序列中沒有重複的元素。

輸出格式：假如不存在這樣的方案，輸出"No solution"(不含引号)；否則，輸出兩行，每行描述劃分出的一個等差序列。如果有多個方案，輸出任意一個。

樣例輸入1：

6

4 1 2 7 3 10

樣例輸出1：

1 2 3

4 7 10

思考過程：很好的貪心題，首先，考試的時候并沒有做出來這個題，考完以後，開始搜題解，并沒有搜到，于是陷入思考，想了半天，寫了個暴力，16個點大資料T掉了。

沒辦法，直接看的别人的送出記錄，看了一下别人的代碼，恍然大悟。

題解：因為題目中說要構造兩個等差數列，而且順序還不能變，是以第一個元素一定在某一個序列的開頭，明确這一點後考慮，先确定一個數列，生成此數列為等差數列，然後在把剩下的數按順序加入到第二個序列當中，判斷是否為等差數列。生成第一個等差數列可以用公差相等處理，現在已知确定兩個數就一定可以計算出。在兩個等差數列的公差中，其中一個的公差是固定的，比如說 原序列為{a1,a2,a3,a4,a5} ，那麼考慮生成序列的公差，隻可能是a2-a1  a3-a2, a3-a1 三個當中的一種，因為無論怎麼選，隻要選3個，至少有兩個在同一個序列當中（抽屜原理）。是以就可以枚舉三個公差，判斷可行性。有了第一個序列的公差，很容易生成出第一個序列（要生成到不能再生成），那剩下的一定就是第二個數列。但是，每一次維護第一個序列不一定能找到最優解，比如9 12 0 5 10 15 20 25 30，如果按以上的操作進行，會生成9 12 15 和 0 5 10 20 25 30顯然這不是最優解。現在考慮在生成第一個數列以後，第二個數列不滿足條件時，如何去調整方案。在調整的時候要注意，不能破壞第一個數列的等差數列的合法性，是以就枚舉删除第一個數列的末尾元素，插入到第二個數列中，判斷是否等差，直到數列一被删空。關于維護第二個數列是否等差， 可以記錄每個數的位置，用map暴力記錄公差。

successful hack

12

0 6 12 18 23 24 25 26 27 28 29 30

#，include <bits/stdc++.h>
using namespace std;
int a[30010], n;
bool vis[30010];
void print(vector <int> v){
	for(int i = 0; i < v.size(); i ++) printf("%d ", v[i]);
	printf("\n");
}
bool check(vector <int> v){
	if(!v.size()) return false;
	if(v.size() == 1 || v.size() == 2) return true;
	int d = v[1] - v[0];
	for(int i = 2; i < v.size(); i ++) if(v[i] - v[i-1] != d) return false;
	return true;
}
bool solve(int l, int r){
	vector <int> v1, v2;
	for(int i = 1; i <= n; i ++) vis[i] = 0;
	int d = a[r] - a[l];
	int last = -1, get = a[l];
	for(int i = 1; i <= n; i ++)
		if(a[i] == get) get += d, v1.push_back(a[i]), last = i;
		else vis[i] = 1;
	for(int i = 1; i <= n; i ++) if(vis[i]) v2.push_back(a[i]);
	if(check(v2)){print(v1),print(v2); return true;}
	vis[last] = 1, v1.pop_back(), v2.clear();
	for(int i = 1; i <= n; i ++) if(vis[i]) v2.push_back(a[i]);
	if(check(v2)){print(v1),print(v2);return true;}
	return false;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]);
	if(n == 2) printf("%d\n%d", a[1], a[2]);
	else if(!solve(1,2) && !solve(2,3) && !solve(1,3)) printf("No solution");
	return 0;
}