公路维修问题

由于长期没有得到维修，A国的高速公路上出现了N个坑。为了尽快填补好这N个坑，A国决定对M处地段采取交通管制。为了求解方便，假设A国的高速公路只有一条，而且是笔直的。现在给出N个坑的位置，请你计算，最少要对多远的路段实施交通管制？

输入数据共两行，第一行为两个正整数N、M （2<=N<=15000，M<=N）。第二行给出了N个坑的坐标（坐标值均在长整范围内，按从小到大的顺序给出，且不会有两个点坐标相同）。

const int MAXN = 15000+10;
 
int mul[MAXN];
 
int main(int argc, const char * argv[]) {
    int n,m,pre=0,next;
    cin >>n>>m;
     
    for (int i=0; i<n; i++) {
        cin >>next;
        mul[i] = next - pre;//[0]不算，间距
        pre = next;
    }
    sort(mul+1, mul+n);//从最小间距开始取
    int ans = 0;
    for (int i=1; i<n-(m-1); i++) {//m-1个间隔不算
        ans += mul[i];
    }
    cout <<ans+m;//每段少加 1
     
    return 0;
}

公路维修问题

原文：https://www.cnblogs.com/i-8023-/p/12096175.html