题目大意
略
题目分析
这题我考试的时候没有看到一个条件啊！！！
对于所有数据，都满足$x1\lt x2 \lt \cdots \lt xn-1 \lt xn,1\le s\le n,0\le L\le n-1$ 。
那这道题其实看完题解后并不是很难。（废话）
可以发现，单向移动具有结合性，如图：
那么我们便可以转成一个一个单位线段移动。
不难发现，在不存在$L$的限制时，我们仅有两种走法：
1.从$s$走到最右边再走到最左边
2.从$s$走到最左边再走到最右边
我们只考虑走法2，因为走法1可以通过翻转一下得出答案。
当$L\le s-1$的时候，向左走再走到最右边即可的出最优答案。
否则，我们就需要从右边绕回来，如图：
我们不妨枚举终点$i$，当$s-1+n-i\ge L$时，不难发现按照上图即为最优方案。
然而当$s-1+n-i\lt L$时这就不管用了，我们还需要在别的地方绕圈，显然我们不会在黄色区域绕圈，因为每个点只可能经过一次，所以我们只可能在绿色区域绕圈：
那么我们用堆维护绿色区域单位线段的最小值绕一下就可以得出答案。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
int n,L,s,a[200005];
int Solve() {
priority_queue<int,vector<int>,greater<int> >Q;
if(L<=s-1)return abs(a[n]-a[1]+a[s]-a[1]);
int tmp=2*abs(a[n]-a[1])-abs(a[s+1]-a[s]),ans=tmp;
for(int i=s+2; i<=n; i++) {
tmp-=abs(a[i]-a[i-1]);
Q.push(abs(a[i]-a[i-1]));
while(s-1+n-i<L) {
L--;
tmp+=2*Q.top();
Q.pop();
}
ans=min(ans,tmp);
}
return ans;
}
int main() {
n=Get_Int();
L=Get_Int();
s=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
if((s!=1&&L==0)||(s!=n&&L==n-1)) {
puts("-1");
return 0;
}
int ans=Solve();
reverse(a+1,a+n+1);
L=n-1-L;
s=n-s+1;
printf("%d\n",min(ans,Solve()));
return 0;
}
|
