uva 10730 - Antiarithmetic?

点击打开链接uva 10730

思路：枚举等差中项
分析：
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;
}