暴力做法时间复杂度O(n^3logn)大于O(n^2),所以只能过一部分的数据,但能得一部分得分数
想一下如何优化? 很多地方可以优化,优化枚举变量,减少枚举变量,这个优化比较复杂。优先考虑判断的过程如何优化(本题可利用数学规律)
暴力做法的优化:因为没有重复的数,并且区间内排序后为递增序列差值为1,因此可以转化为区间最大最小值作差等于区间长度,即max-min = j - i
暴力做法 可以运行,但是超时(蓝桥杯系统得60分)
#include <iostream>
#include <algorithm> //里面有sort(),排序函数
#include <cstring>
using namespace std;
const int N=10010;
int a[N],bac[N];
int main()
{
int n,res=0;
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++){
memcpy(bac,a,sizeof a); // 这里要把数组的初始状态存在bac数组中,因为每次sort排序后,数组的顺序会发生改变。
sort(a+i,a+j+1);
bool flag=true;
for(int k=i;k<j;k++){
if(a[k+1] - a[k] != 1){
flag=false;
break;
}
}
if(flag) res++;
memcpy(a,bac,sizeof a); // 还原数组a的初始状态
}
cout << res << endl;
return 0;
}
暴力做法的优化
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, INF = 100000000; // INF只要大于最大值就行
int n;
int a[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++ ) cin >> a[i];
int res = 0;
for (int i = 0; i < n; i ++ ) // 枚举区间左端点
{
int minv = INF, maxv = -INF;
for (int j = i; j < n; j ++ ) // 枚举区间右端点
{
minv = min(minv, a[j]);
maxv = max(maxv, a[j]);
if (maxv - minv == j - i) res ++ ;
}
}
cout << res << endl;
return 0;
}
为什么不能直接用备份数组,两次memcpy浪费时间
因为如果不备份的话,题目中给出的区间在每次sort之后都会变,变了的话就不是求原来排列的连号区间了
循环内的第一句memcpy应该可以移出 back在循环过程应该不会改变
60%不错了,主要是 暴力,比较容易得分,
为什么 int minv = INF, maxv = -INF;要放到第一个for循环后面呢,放在其他位置为啥就错了呢
因为第二个for循环里minv和maxv的值会变,但是你要保证枚举每个区间时minv和maxv的初始值要是最大和最小,所以要放到第一个for循环后面。
大佬,我觉得INF = 100000000其实写成1e8好看一点
哈哈,1e8确实更好看。