题意：N个人过河，船每次只能坐两个人，船载每个人过河的所需时间不同t[i]，每次过河的时间为船上的人的较慢的那个，问最快的过河时间。(船划过去要有一个人划回来)
#include<iostream> #include<algorithm> using namespace std; int mintime(int t[], int n) { sort(t, t + n); int sum = 0; int i; if (n > 2) { for (i = n; i > 2; i -= 2) { sum += min(t[i - 1] + t[i - 2] + 2 * t[0], 2 * t[1] + t[0] + t[i - 1]); } } if (i == 2) { sum += t[1]; } if (i == 1) { sum += t[0]; } return sum; } int main() { int a[] = { 1,2,3,4 }; int b[] = { 1,2,99,100 }; cout << mintime(a, 4)<<endl; cout << mintime(b, 4); }
对结果稍加观察可以发现，该问题选择哪种方案取决于数据的离散程度，当离散程度大的时候（大的特别大，小的特别小）选择二方案最优，当离散程度小的时候，选择一方案最优。
