题目链接
题目概述
定义连号区间为：某个区间按序排列后，其元素为“连续”的。求一个全排列中连号区间的数目。
题目分析
迭代 l 和 r ，找出区间 [l, r] 的最大值和最小值，判断区间和与“从最小值到最大值的连续数之和”是否相当。
完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <bits/stdc++.h>
using namespace std;
int nums[50005];
int n, ans;
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++)
scanf("%d", &nums[i]);
for(int j=1; j<=n; j++){
int M=INT_MIN, m=INT_MAX;
int sum=0;
for(int i=j; i<=n; i++){
sum+=nums[i];
M=max(M, nums[i]);
m=min(m, nums[i]);
if(sum==(m+M)*(M-m+1)/2.0){
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
|
自我总结
比较简单，要注意 sum==(m+M)*(M-m+1)/2.0 是2.0。