T298571 单峰序列问题咨询
  • 板块题目总版
  • 楼主luogu3032
  • 当前回复0
  • 已保存回复2
  • 发布时间2024/4/12 19:25
  • 上次更新2024/4/12 19:40:04
查看原帖
T298571 单峰序列问题咨询
1208313
luogu3032楼主2024/4/12 19:25

目前是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
2024/4/12 19:25
加载中...