cqyz oj | 潜水比赛 | 贪心

2019-08-03

cqyz oj | 潜水比赛 | 贪心

| 贪心,www.debugger.wiki' style='color:#ffffff' target='_blank'>cqyz oj |

cqyz oj | 潜水比赛 | 贪心

|

cqyz oj | 潜水比赛 | 贪心

Description

  在马其顿王国的ohide湖里举行了一场潜水比赛.其中一个项目是从高山上跳下水,再潜水到达终点.这是一个团体项目,一支队伍由n个人组成.在潜水时必须使用氧气瓶,但是每支队伍只有一个氧气瓶.最多两个人同时使用一个氧气瓶,但此时两人必须同步游泳,因此到达终点的时间等于较慢的一个单独游到终点所需要的时间.好在大家都很友好,因此任何两个人都愿意一起游泳.安排一种潜水策略,使得最后一名选手尽早到达终点。

Input

  第1行:一个整数n,表示队伍的人数。  以下n行,每行一个整数,表示第i个人游到终点的时间Ti(0<=n,Ti<=1000)。

Output

  队伍最早到达终点的时间。

Sample Input 1

3
1
3
4

Sample Input 2

6
1
2
5
6
8
9

Sample Output 1

8

Sample Output 2

27


这题隐含了题意:瓶子去了得有人潜水送回来

先排序
至少有4个人的时候,2种贪心策略取最优:
1、最快的人把最慢的两个人分别运过去再回来,耗时T[n]+T[1]+T[n-1]+T[1]
2、最快和次快的人先过去,其中一个回来,最慢的两个一起过去,另一个再把瓶子带回来,耗时T[2]+T[2]+T[n]+T[1]

#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[1005],sum=0;
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    while(n>=4){
        sum+=min(a[1]*2+a[n]+a[n-1], a[2]*2+a[1]+a[n]);
        n-=2;
    }
       //少于4个人直接讨论
    if(n==3)sum+=a[1]+a[2]+a[3];
    else sum+=a[2];//n==2
    printf("%d",sum);
    return 0;
}

cqyz oj | 潜水比赛 | 贪心

|

cqyz oj | 潜水比赛 | 贪心

|

cqyz oj | 潜水比赛 | 贪心

|

cqyz oj | 潜水比赛 | 贪心

|

cqyz oj | 潜水比赛 | 贪心

cqyz oj | 潜水比赛 | 贪心

| 贪心,www.debugger.wiki' style='color:#ffffff' target='_blank'>cqyz oj |

cqyz oj | 潜水比赛 | 贪心

|

cqyz oj | 潜水比赛 | 贪心

原文地址:https://www.cnblogs.com/de-compass/p/11294680.html