题解归档 - cf427E

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf427E
• 本地来源：problems/cf427E/idea.md
• 题目链接：https://codeforces.com/contest/427/problem/E
• 原始标题：cf427E — Police Patrol

思路

cf427E — Police Patrol

题意

在数轴上选整数点建警局，警车容量 m，每次从警局出发抓至多 m 人再回警局。罪犯坐标已排序，不会逃跑；警局建在罪犯位置则当场抓获。求最小总行驶距离。

固定警局位置 st 的贪心

左右独立：每趟在剩余罪犯中取离警局最远的连续至多 m 个：

• 左：s[p]<st 时一批 p..q-1（q 向右至多 m 个），代价 2(st-s[p])，p=q
• 右：对称，代价 2(s[p]-st)，p=q

calc(st) 线性扫描，正确性：每趟必须覆盖当前最远点，多抓更近的人不会更优。

最优位置

f(st) 在整数轴上凸，在 [s[1],s[n]] 上三分（while(hi-lo>2)），再比较 lo..hi 剩余候选。

复杂度

• 单次 calc：O(n)
• 三分约 O(log 坐标范围) 次，总 O(n)

实现要点

• n,m 可达 10^6，scanf/printf
• 距离 long long；更新答案用 if(pd<ans) 避开 Windows min 宏
• 循环计数勿命名 c

验证

• 官方样例 4 组 AC
• Python 暴力枚举 [s[1],s[n]] 对拍一致

代码

来源：problems/cf427E/solution.cpp

/* Author: likely
 * Time: 2026-06-08 04:51:12
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=1e6+5;
ll n,m,i,j,k,zc,pd,cur,dq,cnt,ans,lo,hi,po1,po2,c1,c2;
ll s[maxn+5];
ll calc(ll st){
    ll res=0,p,q,ct;
    p=1;
    while(p<=n and s[p]<st){
        q=p;
        ct=0;
        while(q<=n and s[q]<st and ct<m){
            q++;
            ct++;
        }
        res+=2*(st-s[p]);
        p=q;
    }
    p=n;
    while(p>=1 and s[p]>st){
        q=p;
        ct=0;
        while(q>=1 and s[q]>st and ct<m){
            q--;
            ct++;
        }
        res+=2*(s[p]-st);
        p=q;
    }
    return res;
}
int main(){
    scanf("%lld%lld",&n,&m);
    for(i=1;i<=n;i++) scanf("%lld",&s[i]);
    lo=s[1],hi=s[n];
    while(hi-lo>2){
        po1=lo+(hi-lo)/3;
        po2=hi-(hi-lo)/3;
        c1=calc(po1);
        c2=calc(po2);
        if(c1<=c2) hi=po2;
        else lo=po1;
    }
    ans=calc(lo);
    for(cur=lo+1;cur<=hi;cur++){
        pd=calc(cur);
        if(pd<ans) ans=pd;
    }
    printf("%lld\n",ans);
    return 0;
}