果然是阅读理解杯…题目看了好几次都不知道在讲什么东西 害…
后来终于看懂了,给的数据一定是有1~n的数组元素,然后1~n这几个数的排列顺序不按照自然数排列,所以才会要判断是否有连号区间.(在递增的条件下)一个数i在给出的序列中的下标与另外一个数j的下标相减再加1,这个长度能等于从i数到j的长度,就是连号区间(阅读理解好累).
所以我们可以得到一个公式:a[i](大的数)-a[j](小的数) = i - j这两个数就形成连号区间.(果然是打表找规律,暴力出奇迹) 最小值和最大值差的就是下标,题目中的加一是指长度.例如1 2 3,3个数,但是3-1=2.
有了这个公式之后我们只需要去枚举就好了.
ps:题目解释里面那个1234…是指下标,不是数字,给它绕了好久....
C++ 代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 10010;
int a[N];
int n;
int res;
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; i++){
scanf("%d",&a[i]);
}
//要将两个数递增排列,相当于找出最大值和最小值.
int ma = 0;//常用技巧:便于更新最大值和最小值
int mi = 10010;
for(int i = 1; i <= n; i++){
//每一轮循环过后都要重新将max和min赋值,否则将会保存上一次的最大值和最小值.
ma = 0;
mi = 10010;
for(int j = i; j <= n; j++){//一个数只能往右去枚举,全部枚举一遍会有重复的比较,所以j = i
ma = max(a[j],ma);
mi = min(a[j],mi);
if((ma - mi) == (j - i)){
res ++;
}
}
}
printf("%d",res);
return 0;
}