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

2019/03/20 10:50

### 样例解释

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题解：

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