P12675

题解

诡异的贪心。

有四种策略：

将头尾并成一样的，直接全赋值为 $-10^{9}$ ；
处理开头一段和结尾一段，使得这两段直接并在一起。
处理开头一段和结尾一段，将端点后的元素加成相同的，赋值中间一段。
处理开头一段和结尾一段，此时开头结尾这两段全为 $-10^{9}$ ，取这两段的最靠近端点赋值中间一段。

对于一个点

i

，可以处理它与

a_{1}

的差值

s_{i}

和与

a_{n}

的差值

c_{i}

。

先预处理

ans

为第一策略的答案。

处理前缀

s_{i}

最小值

M_{i}

，容易发现由于这个数组是

1\sim n

的排列，因此会有两个位置满足

s_{x}=s_{y}=M_{i}

的情况，可以开两个变量存储这两个位置。当枚举到

i

作为右端点时，依次考虑这两个位置的最小贡献（第三、第四策略，注意左右端靠在一起和左右端中间只有一个位置的情况不能使用），并且特判左端点右端点靠在一起的情况即可（第二策略）。

补：贪心证明

可以发现答案至少为

n

，考虑最小化多出来的答案。

处理完前后两端后，此时用上文第二个策略可以使得多余贡献至多为

2

，对于中间任意一个位置，考虑使端点前后的位置与它相等，至少加

2

次，不会更优。

考虑让端点前后的点相等，可以只加一次，可能会更优。对于端点靠在一起的情况不需要多余操作，也会更优。

代码

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e6+5;
const ll inf=1e15;
int _;
int n;
ll a[N],c1[N],c2[N],ans;
ll mnc,pl1,pl2;
void solve() {
	memset(c1,0,sizeof c1),memset(c2,0,sizeof c2);
	scanf("%d",&n),mnc=inf,pl1=pl2=0;
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	ans=abs(a[n]-a[1]);
	for(int i=2;i<n;i++) {
		c1[i]=abs(a[i]-a[1]),c2[i]=abs(a[n]-a[i]);
		if(i>2) ans=min(ans,c2[i]+c1[i-1]);
		if(pl1!=i-1&&pl1!=i-2) ans=min(ans,c2[i]+mnc+min(2ll,abs(a[pl1+1]-a[i-1])));
		if(pl2!=i-1&&pl2!=i-2) ans=min(ans,c2[i]+mnc+min(2ll,abs(a[pl2+1]-a[i-1])));
		if(c1[i]<mnc) pl1=i,pl2=0,mnc=c1[i];
		if(c1[i]==mnc) pl2=i;
	}
	printf("%lld\n",ans+n);
	return;
}
int main() {
	scanf("%d",&_);
	while(_--) solve();
	return 0;
}

文章操作

题解

代码

相关推荐

评论

P12675