题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) O(n2)
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long LL;
const int N = 1e5+10;
int n;
int a[N],b[N];
PII children[N];
int main()
{
int T;
cin>>T;
while(T--)
{
cin>>n;
for(int i = 0;i < n;i ++)
{
cin >> a[i];
children[i]= {a[i],i};
}
sort(children,children + n);
for(int i = 0; i < n ; i++)
{
auto c = children[i];
int left = (c.second + n -1) % n , right = (c.second + 1) % n;
int lv = 1, rv = 1;
if(c.first > a[left]) lv = b[left] + 1;
if(c.first > a[right]) rv = b[right] + 1;
b[c.second] = max(lv,rv);
}
LL res = 0;
for(int i = 0;i < n; i++)
res += b[i];
cout<<res<<endl;
}
return 0;
}