问题描述
小明是一个地理学家，经常要对一段河流进行测量分析。他从上游开始向下游方向等距离地选择了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
样例输出
4
数据范围
对于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
", 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
", ans);
return 0;
}