目前是90分,两个例子过不去,怎么也找不到错误的地方了。自己编了一些测试例子,都能通过。求助大家提供思路。 代码如下:
#include<bits/stdc++.h>
using namespace std;
int main(){
long long n;
cin>>n;
long long a[n] = {}, k[n]={};
long long last_index = 0, last_length = 0, length = 1;
long long i = 0;
long long flatWidth = 1;
//记录最底部的长度,加到下个序列周期的长度上
int preFlatStatus = 1;
//记录前一次持平序列的状态,0代表未结束,1代表已结束。
int down_flag = 0;
//记录当前序列是否出现过下降,0为未出现,1为已出现
// input number
for(i=0; i<n; i++)
{
cin>>a[i];
}
// get xielv
k[0] = 0;
cout << "debug1:" << endl;
cout << k[0] <<" ";
for(i=1; i<n; i++)
{
if(a[i-1] < a[i])
{
k[i] = 1;
cout << k[i] << " ";
}
else if(a[i-1] == a[i])
{
k[i] = 0;
cout << k[i] << " ";
}
else {
k[i] = -1;
cout << k[i] << " ";
}
}
cout << endl;
// get max-length dianfeng series,控制变量dir,k[i];结果变量length,index, last_length,last_index
for(i=1; i<n; i++)
{
//序列模式符合出现下降且当前升高的情况,序列结束,对应计数,新序列开始。
if(down_flag==1 && k[i]>0)
{
if(length > last_length)
{
last_length = length;
last_index = i - last_length;
}
down_flag = 0;
cout <<"Wave End: " << i << " "<< length<<" "<<down_flag<<endl;
length = flatWidth + 1;
}
//序列模式是持续下降、先升后降的情况,更新down_flag,序列继续往后增加
else if(down_flag==0 && k[i]<0)
{
length++;
down_flag = 1;
cout <<"debug3-2: " << i << " "<< length<<" "<<down_flag<<endl;
}
//序列模式是持续上升的情况,序列继续往后增加
else
{
length++;
cout <<"debug3-3: " << i << " "<< length<<" "<<down_flag<<endl;
}
//每次都计算最新的bottom_width;在一个序列周期内,如果只有一个flat序列,宽度增加;如果出现第二个,宽度重新初始化。
if (preFlatStatus==0 && k[i]==0)
{
flatWidth++;
cout <<"Flat wave Continue: " << i << " "<< preFlatStatus<<" "<<flatWidth<<endl;
}
//前一个持平序列关闭
else if(preFlatStatus==0 && k[i]!=0)
{
preFlatStatus=1;
cout <<"Flat wave End: " << i << " "<< preFlatStatus<<" "<<flatWidth<<endl;
}
//出现新的持平序列,状态充值,宽度初始化为1
else if(preFlatStatus == 1 && k[i] ==0)
{
preFlatStatus = 0;
flatWidth = 2;
cout <<"Flat wave Start: " << i << " "<< preFlatStatus<<" "<<flatWidth<<endl;
}
}
// for the last time
if(length > last_length)
{
last_index = n - length;
last_length = length;
cout <<"Last Wave End: " << i << " "<< length<<" "<<down_flag<<endl;
}
cout<<"Result: "<<last_index+1 <<' '<<last_length <<endl;
// cout<< last_length;
return 0;
}
自编的测试案例:
1,无重复
1.1 一个数:1 1
1
1
1.2 多个数: 1 3
3
1 2 3
1.3先增后减: 1 5
5
1 2 3 4 3
7
1 2 3 7 6 5 4
1.4两个峰值:5 9
13
1 2 3 2 1 2 3 4 5 4 3 2 1
2,有重复
2.1 一个数: 1 2
2
1 1
2.2 多个数
3
1 1 1
2.3先增后减 : 1 10 | 1 20
10
1 2 2 3 3 3 3 4 3 2
20
1 1 1 2 2 2 3 3 3 3 7 7 7 7 7 6 6 5 4 4
1.4两个峰值: 9 21
29
1 1 2 2 3 3 2 2 1 1 2 2 3 3 3 4 4 5 5 5 4 4 3 3 2 1 1 1 1
1.5 三个峰值:19 22
40
1 1 2 2 2 3 3 2 2 1 1 2 2 2 3 3 3 2 1 1 1 2 2 2 3 3 3 4 4 4 4 5 5 5 4 3 2 2 2 1
1.6 四个峰值: 19 22
45
1 1 2 2 2 3 3 2 2 1 1 2 2 2 3 3 3 2 1 1 1 2 2 2 3 3 3 4 4 4 4 5 5 5 4 3 2 2 2 1 2 2 2 3 3