题目描述

在遥远的Lineland国家，有N个城市沿直线高速公路排列。高速公路是单向的，只能从编号小的城市驶向编号大的城市。新总统希望在不改变原有单向规则的前提下，通过修建两条新的单向高速公路，使得任意两个城市之间可以互相到达。新建的高速公路不能经过其他城市，且四条端点必须互不相同。求满足条件的最短总修建长度。

输入格式

第一行输入城市数量N（2 ≤ N ≤ 50,000）
第二行输入N-1个整数，表示第2到第N个城市距离第一个城市的距离（严格递增）

输出格式

若无法满足条件，输出0
否则第一行输出最小总长度，第二行输出四条端点编号（格式：S1 E1 S2 E2）

示例分析

输入：

4
3 5 10

输出：

12
3 1 4 2

解释：修建3→1和4→2两条高速公路，总长度= (3-0)+(10-5)=12

解题思路

1. 可行性判断：当N=2时不可行（需要至少两条边但只有两个城市）；N≥3时均可构造解
2. 最优解构造：
   • 对于N≥4的情况，最优解通常为连接首尾和次首次尾（如N→1和(N-1)→2）
   • 对于N=3的情况，需要特殊处理（如3→1和2→1）
3. 数学推导：总长度计算为(X[N]-X[1]) + (X[N-1]-X[2])

C++代码实现

#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int f[50000], sum=0, min, k=1;
    for(int i = 0; i < n-1; i++){
        cin >> f[i];
    }
    for(int i = n-2; i > 0; i--){
        f[i]=f[i]-f[i-1];
    }
    for(int i = 0; i < n-1; i++) sum += f[i];
    min = 2*1e9;
    for(int i = 1; i < n-2; i++){
        if (f[i] < min){
            min=f[i];
            k=i;
        }
    }
    sum += min;
    if(n < 4){
        cout << "0" << endl;
    } else {
        cout << sum << endl;
        cout << k+2 << " " << "1" << " " << n << " " << k+1 << endl;
    }
}

算法标签

#图论 #构造算法 #贪心算法 #最优化