题目描述

在一个大晴天，Oliver与同学们一共N人出游，他们走到一条河的东岸边，想要过河到西岸。而东岸有一条小船。
　　船太小了，一次只能乘坐两人。每个人都有一个渡河时间T，船划到对岸的时间等于船上渡河时间较长的人所用时间。
　　现在已知N个人的渡河时间T，Oliver想要你告诉他，他们最少要花费多少时间，才能使所有人都过河。
　　注意，只有船在东岸（西岸）时东岸（西岸）的人才能坐上船划到对岸。

输入

输入文件第一行为人数N，以下有N行，每行一个数。
第i+1行的数为第i个人的渡河时间。

输出

输出文件仅包含一个数，表示所有人都渡过河的最少渡河时间

思路

递推，f[i]=min(f[i−1]+a[1]+a[i],f[i−2]+a[1]+a[2]∗2+a[i])
而且不用排序。。。。。。。。。

pascal

var
  a,f:array[0..1000000] of int64;
  i,j,k,n,m,s,x,y:longint;
  mi:int64;
function min(x,y:int64):int64;
begin
  if x

c++

#include 
using namespace std;
long long a[1000000],f[1000000];
int i,j,k,n,m,s,x,y;
long long ans;
__attribute__((optimize("O2")))
int min(int x,int y)
{
    if (x>y) return y;
    else return x;
}
__attribute__((optimize("O2")))
int main()
{
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[1]=a[1];
    f[2]=a[2];
    for (i=3;i<=n;i++)
    {
         f[i]=min(f[i-1]+a[1]+a[i],f[i-2]+a[1]+a[2]*2+a[i]);
    }
    printf("%d\n",f[n]);
    return 0;
}