【u215】河床

问题描述

小明是一个地理学家，经常要对一段河流进行测量分析。他从上游开始向下游方向等距离地选择了N个点测量水位深度。得到一组数据d1,d2,……,dn，回到实验室后数据分析员根据需要对数据进行分析，发掘隐藏在数据背后的规律。最近，小明发现某种水文现象与河床地势有关，于是他指示分析员要找出一段河流中最大高低起伏差不超过K(k<=100)的最长的一段。这看似一个复杂的问题，由于任务紧急，分析员求助于你，并告诉你小明的所有数据，数据都精确到个位。

输入格式

输入文件riverbed.in包含2行，第一行是整数N和k，分别表示测量点的个数和博士要求的最大水深差(也就是河床地势差)。第二行有N个整数，表示从上游开始一次得到的水位深度为di。

输出格式

输出文件riverbed.out只有一行，是正数M，表示最长一段起伏不超过K的河流长度，用测量点个数表示。

样例输入

6 2

5 3 2 2 4 5

样例输出

数据范围

对于100%的数据有 N <= 30000，di <= 32767以及K <= 100

【解法一：数据结构】

正常的思路。

从每一个位置i，开始往后尝试。看看最长能够扩展多长的序列。

但是每个位置都要重新开始找一遍。会超时。

数据结构！

队列？OK

堆？OK

为啥用队列？因为是一段序列嘛。

为啥用堆？涉及到最大值和最小值。用大根堆小根堆来维护。

先把数据读入a数组

然后从1->n依次把每一个元素都加入到队列的尾端。

如果加入到尾端之后。我们用堆维护的最大值减去最小值大于k了。

则头结点一直递增(即从队列的前面把一些数字去除掉)。注意这个时候堆也会发生变化！

知道我们用堆维护的最大值和最小值的差小于等于k。

尝试用tail-head+1来更新解。

然后再继续加入元素到队列的尾端。

重复上诉过程。

//这个过程就相当于for i =1 to n 然后j=i+1，j一直往后枚举的效果。

//只不过用了队列和堆让操作简化了。即少了j这一层循环。

//对应的变成了队列头尾节点的移动。

当然。加入元素的时候。也要调整堆。

堆的操作会比较麻烦。但只要熟悉掌握了堆。代码不会难打。

看似很长的程序。其实就是几个堆的操作。

然后建议不要把大根堆和小根堆的操作合在一起。不然会有点乱。

【代码1】

#include <cstdio>

struct data

{

	int what, height; //what是堆中这个数据height对应的一开始输入到数组的下标。

};//这个what是为了调整各个元素在堆中的位置。

int head, tail,n,k,a[30001],dl[30001];

int size_dagendui = 0, size_xiaogendui = 0,pos,ans = 0;

int posdagendui[30001],posxiaogendui[30001]; //某个元素(下标)在大根堆或小根堆中的位置。

data dagendui[30001], xiaogendui[30001];

void input_data()

{

	scanf("%d%d", &n, &k); //n表示n个数据。k表示最大水位差。

	for (int i = 1; i <= n; i++)

		scanf("%d", &a[i]);

}

void up_adjustda(int p) //大根堆从位置p开始往上调整

{

	int x = dagendui[p].height;

	data temp = dagendui[p]; //把整个位置p的东西全都记录下来

	int i = p, j = p / 2;

	while (j > 0)

	{

		if (dagendui[j].height < x) //如果父亲比儿子小就不满足大根堆了。

		{

			dagendui[i] = dagendui[j];

			posdagendui[dagendui[j].what] = i; //要调整这个元素在堆中的位置。

			i = j;

			j = i / 2;

		}

		else

			break;

	}

	pos = i; //方便再往下调整。新添加一个元素在堆的末尾要先往上调整到位置pos，然后从位置pos再

	//尝试往下调整。

	dagendui[i] = temp; //调整刚才记录的元素的位置。

	posdagendui[temp.what] = i; //记录的东西也要调整。

}

void down_adjustda(int p) //从位置p往下调整大根堆

{

	int x = dagendui[p].height;

	data temp = dagendui[p]; //整个记录下来。

	int i = p, j = i * 2;

	while (j <= size_dagendui)

	{

		if (j<size_dagendui && dagendui[j + 1].height>dagendui[j].height) //如果j+1的数据更大

			j++; //则换成j+1.因为这样如果要调整 调整到根的数据会是最大的。

		if (x < dagendui[j].height) //如果儿子比爸爸大。则不正常。往上调整。

		{

			dagendui[i] = dagendui[j];

			posdagendui[dagendui[j].what] = i; //重新记录被调整的东西的位置。

			i = j;

			j = i * 2;

		}

		else

			break;

	}

	dagendui[i] = temp;//刚才记录的东西全都赋值到新的位置。

	posdagendui[dagendui[i].what] = i; //重新记录位置

	pos = i;

}

void up_adjustxiao(int p) //往上调整小根堆 。具体的同上 这个过程不再写注释。

{

	int x = xiaogendui[p].height;

	data temp = xiaogendui[p];

	int i = p, j = p / 2;

	while (j > 0)

	{

		if (xiaogendui[j].height > x)

		{

			xiaogendui[i] = xiaogendui[j];

			posxiaogendui[xiaogendui[j].what] = i;

			i = j;

			j = i / 2;

		}

		else

			break;

	}

	xiaogendui[i] = temp;

	posxiaogendui[temp.what] = i;

	pos = i;

}

void down_adjustxiao(int p) //往下调整小根堆 。具体的同上 这个过程不再写注释。

{

	int x = xiaogendui[p].height;

	data temp = xiaogendui[p];

	int i = p, j = i * 2;

	while (j <= size_xiaogendui)

	{

		if (j < size_xiaogendui && xiaogendui[j + 1].height < xiaogendui[j].height)

			j++;

		if (x > xiaogendui[j].height)

		{

			xiaogendui[i] = xiaogendui[j];

			posxiaogendui[xiaogendui[j].what] = i;

			i = j;

			j = i * 2;

		}

		else

			break;

	}

	xiaogendui[i] = temp;

	posxiaogendui[temp.what] = i;

	pos = i;

}

void get_ans()

{

	int head = 0, tail = 0;

	for (int i = 1; i <= n; i++) //把输入的n个数据尝试加入队列尾端。

	{

		size_dagendui++; //加入到大根堆中

		dagendui[size_dagendui].height = a[i];

		dagendui[size_dagendui].what = i;

		up_adjustda(size_dagendui);//先往上调整

		down_adjustda(pos); //再从调整后的位置往下调整

		size_xiaogendui++; //加入到小根堆

		xiaogendui[size_xiaogendui].height = a[i];

		xiaogendui[size_xiaogendui].what = i;

		up_adjustxiao(size_xiaogendui);

		down_adjustxiao(pos); //同样先往上调整再往下调整。

		if (head == 0)//如果是第一个元素。头结点也要变成1.

		{

			head = 1;

			dl[head] = i;

		}

		tail++; //只递增尾节点。

		dl[tail] = i;

		while ((dagendui[1].height - xiaogendui[1].height) > k) //如果超过了限制。

		{

			int key = dl[head]; //取出头结点

			dagendui[posdagendui[key]] = dagendui[size_dagendui];//把堆中的最后一个元素放在

			size_dagendui--; //这个头结点在堆中的位置。代替它。也即删除这个元素

			up_adjustda(posdagendui[key]);//然后先尝试往上调整。

			down_adjustda(pos);//然后从调整过后的位置再往下调整

			xiaogendui[posxiaogendui[key]] = xiaogendui[size_xiaogendui];

			size_xiaogendui--; //大根堆小根堆中的对应元素都要删掉。

			up_adjustxiao(posxiaogendui[key]);

			down_adjustxiao(pos);

			head++; //头结点递增。表示刚才的头结点所在的元素已经删掉了。

		}

		if ((tail - head + 1) > ans)//尝试用尾节点和头结点的差+1来更新答案。

			ans = (tail - head + 1);

	}

}

void output_ans()

{

	printf("%d\n", ans);

}

int main()

{

	//freopen("F:\\rush.txt", "r", stdin);

	//freopen("F:\\rush_out.txt", "w", stdout);

	input_data();

	get_ans();

	output_ans();

	//fclose(stdin);

	//fclose(stdout);

	return 0;

}

【解法二：动态规划】

设f[i][j]表示

以a[i]作为序列的最后一个元素。最小值为a[i]-j,最大值为a[i]-j+k所能达到的最长序列长度。

先用前一个元素a[i-1]减去最小值(a[i]-j)设为judge

然后若是judge>=0 且 judge <= k。

则表示a[i-1]在[a[i]-j,a[i]-j+k]这个范围内。

则可以把后面这个元素接在前面那个元素后面。

即f[i][j] = f[i-1][judge]+1;

这里a[i-1]-judge == a[i]-j;

因为已经确认了judge >= 0且judge <=k;

所以可以确定f[i-1][judge]这个状态是存在的。

这个状态是存在的。再把a[i]加上去。这个状态还是不会变的。

所以满足状态转移关系。

原理在于此。

如果一个序列中存在a[i]；

则它的最小值不会大于a[i]-k;

即它的最小值只可能是a[i]-k到a[i]这些数字。

然后对应得最大值直接加上k就可以了。

由这个规律。我们可以枚举每个元素作为最后一个元素它的最小值。

然后看一下前一个元素是否能在这个序列中。

//枚举一个还不存在将要存在的序列。

【代码2】

#include <cstdio>

int n, k,ans = 1;

int a[30001], f[30001][101];

int main()

{

	scanf("%d%d", &n, &k);

	for (int i = 1; i <= n; i++)

		scanf("%d", &a[i]);

	for (int i = 0; i <= k; i++) //这是只有一个元素的情况。最小值为多少都可以。

		f[1][i] = 1;

	for (int i = 2; i <= n; i++)

		for (int j = 0; j <= k; j++)

		{

			int judge = a[i - 1] - (a[i] - j); //前面一个元素和这个序列的最小元素比较。

			if (judge >= 0 && judge <= k)//如果比它大，且不超过k。则可以把前一个元素接上来。

			{

				f[i][j] = f[i - 1][judge] + 1;

			}

			else

			{

				f[i][j] = 1; //否则单独成一个序列

			}

			if (f[i][j] > ans)//尝试更新答案。

				ans = f[i][j];

		}

	printf("%d\n", ans);

	return 0;

}

巴特西

【u215】河床

最新文章

热门文章