思路:枚举等差中项
分析:
1 给定一个n个数的序列判断是否有等差子序列
2 很明显我们如果要判断是否有等差子序列的话,只要去判断是否有长度为3的等差子序列
3 对于n<=10000,那么我们怎么去判断呢,由于我们要找的是是否有三个的等差序列,那么我们可以枚举每一个数作为等差中项,然后去判断
4 假设现在我们枚举num[i]作为等差中项,那么第一个数在0~i-1之间,第二个数是在i+1~n-1之间,这个时候如果单存利用for循环去找时间复杂度不能接受,那么我们想到能减少多少复杂度呢?
5 我们知道set内部利用的是红黑数,所以说set的查找是logN的比O(n)快,所以呢我们利用set来找第二个数那么这样降低了时间复杂度。
代码:
#include<set> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int const MAXN = 10010; int n , num[MAXN]; set<int>s; bool solve(){ //枚举每一个数作为等差中项 for(int i = 0 ; i < n ; i++){ //左边 s.erase(num[i]); for(int j = 0 ; j < i ; j++){ //右边 int value = 2*num[i]-num[j]; if(s.find(value) != s.end()) return true; } } return false; } int main(){ char str[10]; while(scanf("%s" , str)){ if(!strcmp(str , "0")) break; sscanf(str , "%d:" , &n); s.clear(); for(int i = 0 ; i < n ; i++){ scanf("%d" , &num[i]); s.insert(num[i]); } printf("%s\n" , solve() ? "no" : "yes"); } return 0; }