p13595 贪心

题目描述

题目描述实在太猎奇了，解释一下题目到底要干嘛。

有n个数，其中每个数互不相同，你可以使值为x的数变成y，两个一样的数可以看一个区间，但代价是|x-y|，你要使所有区间覆盖整个数组。

举个例子

按照体面描述来解释

5
1 4 3 2 5

输出 2

那么首先这个二是哪里来的

第一次调整：选择 x=1,y=2，调整度为 1，旋律变为 2,4,3,2,5。

第二次调整：选择 x=4,y=5，调整度为 1，旋律变为 2,5,3,2,5。

所有调整结束后，位置 1 和位置 4 之间的音符产生共鸣，位置 2 和位置 5 之间的音符产生共鸣，所有音符都至少产生一次共鸣，调整度之和为 2。

那也就是说形成了两个区间，一个是1-4，一个是2-5

这两个区间确确实实覆盖了整个数组

那我们到底是要选哪些区间。

思路

利用贪心思想，我们尽可能不用修改，知道迫不得已，不选就要缺的时候才去修改。

那怎么修改又成了一个问题。

我们深入思考，就会发现，产生共鸣的音符一定是旋律差值是1的

证明

假如有这样一个序列

1 4 2 5 3

我们以直接将1改为3，这样就可以从头到尾一次性覆盖了，但你可别忘了，这个序列的每个数是不重复的。并且1~n每个数都会出现一次。所以我们一样可以将1 3的区间改成1到2，2到3的区间，代价是一样的。所以我们只考虑旋律差值为1的旋律去共鸣。

这时候思路就清晰很多了。代码实现。

这时候我们可以拿一个变量mr，代表1~mr都覆盖了，如果我们这时遍历到i，但是i<=mr，我们该不该选i这个节点去产生共鸣。不能，我们不确定他是否要用得上。只要不是100%能用上的，我们坚决不用。

那什么时候才是100%能用上的呢

就是i>mr的时候,我们就必须要选了

but

不一定是选第i个旋律去共鸣

我们要用一个变量r去保存从1~i产生共鸣（代价为1）可以覆盖最右边的数，使mr=r（更新覆盖至最右边）

没次产生共鸣的时候，ans++

最后输出ans为答案即可

代码

#include<bits/stdc++.h>
using namespace std;
long long n,mr,ans;
long long a[10000010],b[10000010];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[a[i]]=i;
	}
	long long r=0;
	for(int i=1;i<=n;i++)
	{
		r=max({b[a[i]-1],b[a[i]+1],r});
		if(mr<i)
		{
			ans++;
			mr=r;
		}
	}
	cout<<ans;
	return 0;
}