本文主要是介绍10730-Antiarithmetic?【暴力枚举】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
水题
求一个序列是否存在3个数按顺序构成等差数列
直接枚举等差数列的差值 时间复杂度降到 n * n / 3
开pos数组记录每个值得为之
楷vis数组记录目前i是否出现过
强行AC
15221397 | 10730 | Antiarithmetic? | Accepted | C++ | 0.035 | 2015-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;
}
这篇关于10730-Antiarithmetic?【暴力枚举】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!