题意
在一个数轴上有 \(N(1\le N\le 10^5)\) 个点，给定每个点的位置 \(x_i\) (横坐标)，保证 \(x_i\) 单调递增且 \(|x_i|\le 10^8\) 。求从原点出发，到达不同的 \(K(1\le K\le N)\) 个点所经过的最小距离。
分析
我们看到 \(N\) 的范围正好卡掉 \(O(N^2)\) ，但 \(O(N)\) 可以过不然怎么输入，且点都在一条直线上，所以可以考虑直接遍历求解。
事实上，一眼就可以看出来所选的 \(K\) 个点应该是连续的。所以 \(x_i\) 会有三种情况：全为正，全为负或有正有负。设左边界为 \(i\) ，右边界就为 \(i+k-1\) (注意这个-1)。
- 所有 \(x_i\) 都为正数时，如图：
可以得到此时的答案为 \(x_{i+k-1}\) 。 - 所有 \(x_i\) 都为负数时，如图：
可以得到此时答案为 \(x_i\) 。 - 当有正有负时，如图：
可得答案为 \(\min(x_{i+k-1},x_i)+x_{i+k-1}-x_i\) 。
通过对以上的归纳，我们可以发现，最短的路应该是先往 \(|x|\) 小的一边走，再往另一端走或继续向前。所以答案为 \(ans=x_{i+k-1}-x_i+\min(x_{i+k-1},x_i)\) (因为 \(i+k-1\) 一定在 \(i\) 的右边或与 \(i\) 重合，所以 \(|x_{i+k-1}|-|x_i|\) 为正)。
最终，时间复杂度为 \(O(N)\) 。
Code
#include<bits/stdc++.h>
typedef long long ll;//可以不开long long
char buf[1<<21],*p1=buf,*p2=buf,obuf[1<<21],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
using namespace std;
inline ll read(){ll x=0,f=1;char c=getchar();while(c<48||c>57){if(c==45)f=0;c=getchar();}while(c>47&&c<58)x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?x:-x;}
inline void write(ll x){if(x<0)putchar(45),x=-x;if(x>9)write(x/10);putchar(x%10+48);}//以上为模板
ll n,k,x[100005],ans=LONG_LONG_MAX;//注意ans的初始值为极大值
signed main(){
n=read(),k=read();
for(ll i=1;i<=n;++i)x[i]=read();
for(ll i=1;i+k-1<=n;++i){
ans=min(ans,x[i+k-1]-x[i]+min(abs(x[i]),abs(x[i+k-1])));//式子
}
write(ans);
return 0;
}