算法：uva 10730 - Antiarithmetic

算法：uva 10730 - Antiarithmetic2014-03-17 csdn博客 shuangde800题目大意：

给n个数组成的序列，他们是0~n-1，问序列中是否有按顺序的3个数，是等差数列。

思路：

用一个数组记录每个数在序列中的位置，然后枚举3个数中最小的一个，再枚举等差数列的增量，最后看着三个数的位置是不是连续的即可。

n最大为1W，但这个算法的复杂度看起来好像是O（n^2），怎么速度还挺快的呢？粗略的分析一下复杂度吧。

第一层for循环是 0...n，重点是看第二层for循环 : for（int j=1; i+2*j < n; ++j）

把 i+2*j < n 移项改变一下成了：

j < n/（2*i），j就是第二层for循环的枚举次数，我们可以发现，随着i的增大，j会变得越来越小，而且变化速度很快。

当i=1,2,3...n时， j 分别要枚举： n/2, n/4, n/6, n/8, n/10, n/12, ...n/（2*i）次，我们可以发现当i=5时，j 枚举的次数为n/10已经小于n的10倍了，当i=20时j 的次数为n/40, 小于n的40倍了。假设n等于1W，那么当 i=5时，j 要枚举1000次，当i=20时，只要枚举250次，第二层的降速是非常快的。所以这个算法的复杂度是远远小于O（n^2），目测在n log n左右

代码：

#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>using namespace std;const int MAXN = 10010;int n;int arr[MAXN];inline bool judge（int* a）{for（int i=0; i<n; ++i）{for（int j=1; i+2*j<n; ++j）{ //枚举增量if（a[i]<a[i+j]&&a[i+j]<a[i+2*j] || a[i]>a[i+j]&&a[i+j]>a[i+2*j] ）return false;}}return true; } int main（）{int x;while（~scanf（"%d:", &n） && n）{for（int i=0; i<n; ++i）{scanf（"%d", &x）;arr[x] = i;}if（judge（arr）） puts（"yes"）;else puts（"no"）;}return 0;}