解题思路:
其实题目很简单,外层的双重遍历是肯定少不了的,问题就是你在遍历之后进行判断的方法:
错误示范:用sort排序,这样耗时太长,会超时。
其实对于这道题目因为他的数是连续的,所以比较简单,我们可以利用这一点:
只要我们做到:最大值-最小值+1=i - j+1(即你要判断的区间长度)
(1)耗时较多的:用max( )和min( ),来查找,可以通过,我用了这里其他同学的耗时 61.
(2)耗时较少:其实很简单,因为我们的外层的双重遍历肯定是少不了的,我们可以在这个遍历的过程中找到max
和min(代码在下面)。
注意事项: 注意不要超时
核心代码:(这里耗时31,其实这里还可以进行一些合并)
for(int i=0;i<n;i++){ int min=arr[i]; int max=arr[i]; for(int j=i;j<n;j++){ if(i == j) { ans++; continue; } else{ if(arr[j]>max) max=arr[j]; if(arr[j]<min) min=arr[j]; if(max-min+1==j-i+1) ans++; } } }
核心代码2:
for(int i=0;i<n;i++){ int min=arr[i]; int max=arr[i]; for(int j=i;j<n;j++){ if(arr[j]>max) max=arr[j]; if(arr[j]<min) min=arr[j]; if(max-min+1==j-i+1) ans++; } } }
完整参考代码:
#include<iostream> using namespace std; int n; int arr[50000]; int ans=0; int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>arr[i]; } for(int i=0;i<n;i++){ int min=arr[i]; int max=arr[i]; for(int j=i;j<n;j++){ if(arr[j]>max) max=arr[j]; if(arr[j]<min) min=arr[j]; if(max-min+1==j-i+1) ans++; } } cout<<ans; return 0; }
0.0分
3 人评分
C语言训练-阿姆斯特朗数 (C语言代码)浏览:851 |
C语言程序设计教程(第三版)课后习题10.3 (C语言代码)浏览:688 |
简单的a+b (C语言代码)浏览:530 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:885 |
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)from DQM浏览:667 |
简单的a+b (C语言代码)浏览:419 |
C语言程序设计教程(第三版)课后习题10.7 (C语言代码)浏览:664 |
格式化数据输出 (C语言代码)浏览:821 |
计算质因子 (C语言代码)浏览:707 |
C语言程序设计教程(第三版)课后习题12.2 (C语言代码)浏览:766 |