水题
求一个序列是否存在3个数按顺序构成等差数列
直接枚举等差数列的差值 时间复杂度降到 n * n / 3
开pos数组记录每个值得为之
楷vis数组记录目前i是否出现过
强行AC
1522139710730Antiarithmetic?AcceptedC++0.0352015-03-26 12:09:56
#include<cstdio>#include<cmath>#include<cstring>#include<algorithm>using namespace std;const int maxn = 11111;int array[maxn];int vis[maxn];int pos[maxn];int main(){int n;while(scanf("%d",&n) && n){scanf("%*s");memset(vis,0,sizeof(vis));for(int i = 0; i < n; i++){scanf("%d",&array[i]);pos[array[i]] = i;}int d = n / 3;int ok = 0;for(int i = 0; i < n; i++){vis[array[i]] = 1;for(int j = 1; j <= d; j++){int e1 = array[i] – 2 * j;int e2 = array[i] – j;int e3 = array[i] + 2 * j;int e4 = array[i] + j;if(e1 >= 0){if(vis[e1] && vis[e2] && pos[e1] < pos[e2]){//printf("%d %d %d\n",e1,e2,array[i]);ok = 1;break;}}if(e2 < n){if(vis[e3] && vis[e4] && pos[e3] < pos[e4]){//printf("%d %d %d\n",e3,e4,array[i]);ok = 1;break;}}}if(ok){//printf("%d\n",i);break;}}if(ok) printf("no\n");else printf("yes\n");}return 0;}
，阳光总在风雨后。只有坚强的忍耐顽强的奋斗，
