计蒜客 蓝桥杯模拟 快速过河

2019/03/20 10:50
阅读数 29
 

在一个夜黑风高的晚上,有 nn 个小朋友在桥的这边,现在他们需要过桥,但是由于桥很窄,每次只允许不超过两人通过,他们只有一个手电筒,所以每次过桥后,需要有人把手电筒带回来,第 ii 号小朋友过桥的时间为 a_iai,两个人过桥的总时间为二者中时间长者。问所有小朋友过桥的总时间最短是多少。

输入格式

第一行输入一个整数 nn,表示有 nn 个小朋友。

第二行有 nn 个整数 a_iai ,a_iai 表示第 ii 个小朋友过河需要的时间。

输出格式

输出一个整数,表示所有小朋友过河所需要的时间。

随后是你的通过和返回次序,每一行是两个或者三个整数,第一个整数,表示这一行有几个整数,后面的一个或者两个整数对应着人(通过时间代表人),返回也要占一行。

数据范围

对于 30\%30% 的数据:1 \le n \le 51n5。

对于 100\%100% 的数据:1 \le n \le 10001n1000 ,0 < a_i \le 10000<ai1000

样例解释

1717 秒

(1,2)(1,222 秒

(1)(111 秒

(5,10)(5,101010 秒

(2)(222 秒

(1,2)(1,222 秒

本题答案不唯一,符合要求的答案均正确

样例输入复制

4
1 2 5 10

样例输出复制

17
2 1 2
1 1
2 5 10
1 2
2 1 2

题解:

动态规划:
我们先将所有人按花费时间递增进行排序,假设前 i 个人过河花费的最少时间为 opt[i],那
么考虑前i-1个人已经过河的情况,即河这边还有1个人,河那边有i-1个人,并且这
时候手电筒肯定在对岸,所以 opt[i] = opt[i-1] + a[1] + a[i]   (让花费时间最少的人把手
电筒送过来,然后和第i个人一起过河) 。
如果河这边还有两个人,一个是第i号,另外一个无关,河那边有i-2个人,并且手电筒
肯定在对岸,所以 opt[i] = opt[i-2] + a[1] + a[i] + 2*a[2](让花费时间最少的人把
电筒送过来,然后第i个人和另外一个人一起过河,由于花费时间最少的人在这边,所以下
一次送手电筒过来的一定是花费次少的,送过来后花费最少的和花费次少的一起过河,解决
问题),所以 opt[i] = min(opt[i-1]+a[1]+a[i],opt[i-2]+a[1]+a[i]+2*a[2])
贪心:
一个人:时间为a0  。
两个人:时间为a1。
三个人:时间为a0+a1+a2  。
多个人:比较下面两种方案中的最优值。
a[0]*2+a[n]+a[n-1] ? a[0]+2*a[1]+a[n]

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define ls (r<<1)
#define rs (r<<1|1)
#define debug(a) cout << #a << " " << a << endl
using namespace std;
typedef long long ll;
const ll maxn = 1e5+10;
const ll mod = 1e9+7;
const double pi = acos(-1.0);
const double eps = 1e-8;
ll n, sum = 0, a[maxn], dp[maxn];
int main() {
    scanf("%lld",&n);
    for( ll i = 0; i < n; i ++ ) {
        scanf("%lld",&a[i]);
    }
    sort(a,a+n);
    dp[0] = a[0];
    dp[1] = a[1];
    for( ll i = 2; i < n; i ++ ) {
        dp[i] = min( dp[i-1]+a[0]+a[i], dp[i-2]+a[0]+2*a[1]+a[i] );
    }
    printf("%lld\n",dp[n-1]);
    n --;
    while( 1 ) {
        if( !n ) {
            sum += a[0];
            printf("1 %lld\n",a[0]);
            break;
        } else if( n == 1 ) {
            sum += a[1];
            printf("2 %lld %lld\n",a[0],a[1]);
            break;
        } else if( n == 2 ) {
            sum += a[0] + a[1] + a[2];
            printf("2 %lld %lld\n",a[0],a[1]);
            printf("1 %lld\n",a[0]);
            printf("2 %lld %lld\n",a[0],a[2]);
            break;
        } else {
            if( a[0]*2+a[n]+a[n-1]>a[0]+2*a[1]+a[n] ) {
                sum += a[0]+2*a[1]+a[n];
                printf("2 %lld %lld\n",a[0],a[1]);
                printf("1 %lld\n",a[0]);
                printf("2 %lld %lld\n",a[n-1],a[n]);
                printf("1 %lld\n",a[1]);
                n -= 2;
            } else {
                sum += a[0] + a[n];
                printf("2 %lld %lld\n",a[0],a[n]);
                printf("1 %lld\n",a[0]);
                n -= 1;
            }
        }
    }
    return 0;
}

  

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部