大神看下 京东烽火台那个题是怎么搞的

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <unordered_map>
using namespace std;
 int main()
{
    int n;
    cin >> n;
    vector<int> vec(2 * n,0);
    int i = 0;
    int high;
    while (i < n && cin >> high){
        vec[i++] = high;
    }
    int res = n;
    for (i = 0;i < n;++i){
        vec[i + n] = vec[i];
    }
    for (int a = 0;a < n;++a){
        for (int b = a + 2;b < a + n - 1 && vec[a] != vec[b];++b){
            int key = min(vec[a],vec[b]);
            bool isLit = true;
            for (int j = a + 1;j <= b - 1;++ j){
                if (vec[j] > key){
                    isLit = false;
                    break;
                }
            }
            if (isLit) ++res;
            if (isLit)cout << vec[a] << " " << vec[b] <<endl;
        }
    }
    cout << res << endl;
    return 0;
}
n^3的复杂度,思路是相邻的肯定可以,然后穷举任意两个,它们之间的山峰都比a,b的要低,因为是环状,所以是2*n的长度,可以实现环状的效果
#京东##C++工程师#
全部评论
我是在列表前面,增加了一个自己,后面增加了一个自己,实现环 2n^2的复杂度。
点赞
送花
回复 分享
发布于 2016-09-05 21:38

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务