.......想了很久 没想出一个比O（n^2)更快的算法..但我知道 肯定是有O(nlogN)的算法在的 可能需要用到一些高效的数据结构去维护吧
然后 惊心地3900ms水过以后 看到discuss里面 一个人贴了个自己博客地址 去看了下 的确存在... 但有些麻烦=-= 有兴趣的自己可以去点开来看
我的做法的话 就是直接hash了 因为本来o(N^2)就很慢了 所以任何剪枝优化一定要做 比如那个 2数相加是不是为偶数的判断 如果不用的话 应该会tle吧 我懒得去试了
直接上代码吧 这种数学题 其实还是蛮有意思的 不和图论一样 ╮(╯▽╰)╭..
1 #include <iostream> 2 using namespace std; 3 4 const int size = 10010; 5 int hash[size]; 6 7 int main() 8 { 9 cin.sync_with_stdio(false); 10 int t , n , num , mid; 11 bool flag; 12 cin >> t; 13 while( t-- ) 14 { 15 flag = false; 16 cin >> n; 17 for( int i = 1 ; i<=n ; i++ ) 18 { 19 cin >> num; 20 hash[num] = i; 21 } 22 for( int i = 1 ; i<=n-2 ; i++ ) 23 { 24 for( int j = i+2 ; j<=n ; j++ ) 25 { 26 if( (i+j)%2==0 ) 27 { 28 mid = (i+j)/2; 29 if( ( hash[mid]>hash[i] && hash[mid]<hash[j] ) ||(hash[mid]<hash[i] && hash[mid]>hash[j] ) ) 30 { 31 flag = true; 32 break; 33 } 34 } 35 if( flag ) 36 break; 37 } 38 if( flag ) 39 break; 40 } 41 if( flag ) 42 cout << "Y" << endl; 43 else 44 cout << "N" << endl; 45 } 46 return 0; 47 }