本文主要是介绍poj 2573 Bridge(贪心：过河问题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
开始以为排完序每次直接取相邻的就可以了呢
还以为是考察数据结构的题
WA了之后看别人的题解才知道这是一类问题
在这道题目中分析4个人 “a b c d” 过河情况：
把多种情况列出来会发现只有两种情况可能是最优的
第一种：最快的带最慢的
a c
a
a d
a
第二种：最快的带最慢的和次快的带次慢的
a b
a
c d
b
对于n > 3按照上面策略多次处理，每次可以减去两个人
知道n==3 或 n==2为止
n==2时 输出：a b
n==3时 输出：
a b
a
a c
-------------------------------------------------------------------------------------------
代码如下：
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MAXN 1010
using namespace std;int a[MAXN];int main(void) {int n, ans, cost1, cost2;scanf("%d", &n);for(int i=0; i<n; ++i) {scanf("%d", &a[i]);}if(n == 1) {printf("%d\n%d\n", a[0], a[0]);return 0;}sort(a, a+n);int tmp = n;ans = 0;while(tmp > 3) {cost1 = 2*a[0]+a[tmp-1]+a[tmp-2];cost2 = 2*a[1]+a[0]+a[tmp-1];ans += min(cost1, cost2);tmp -= 2;}if(tmp == 2) ans += a[1];else ans += a[0]+a[1]+a[2];cout << ans << endl;while(n > 3) {cost1 = 2*a[0]+a[n-1]+a[n-2];cost2 = 2*a[1]+a[0]+a[n-1];if(cost1 > cost2) printf("%d %d\n%d\n%d %d\n%d\n", a[0], a[1], a[0], a[n-2], a[n-1], a[1]);else printf("%d %d\n%d\n%d %d\n%d\n", a[0], a[n-1], a[0], a[0], a[n-2], a[0]);n -= 2;}if(n == 2) printf("%d %d\n", a[0], a[1]);else {printf("%d %d\n%d\n%d %d\n", a[0], a[1], a[0], a[0], a[2]);}return 0;
}这篇关于poj 2573 Bridge(贪心：过河问题)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
