翻译:有一个整数序列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
using namespace std;
int a[30010], n;
bool vis[30010];
void print(vector v){
for(int i = 0; i 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 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;
}