經典的貪婪。

兩種方案：一個：讓我們來最快，第二快，在過去的第一，最快的回。然后最慢，最慢第二，在過去。次最快的回來a[0]+a[1]+a[1]+a[n-1]

二：最快的和最慢的過去，最快的回來，最快的和當前最慢的過去，最快的回來。

a[0]+a[n-1]+a[0]+a[n-2]

每次取最優解。

注意：最后剩余沒過的人小于等于3的時候。要特殊推斷。

代碼：

#include <cstdio> #include <cstring> #include <algorithm> #define INF 0x3f3f3f3f using std::sort; int s[1005], ans, n;void solve(){ans = 0;int st = 0, en = n, len = 0;while(en > 3){int temp1 = s[en-1]+2*s[1]+s[0];int temp2 = 2*s[0]+s[en-1]+s[en-2];ans += temp1<temp2 ?temp1:temp2;en -= 2;}if(en == 3) ans += s[0]+s[2];ans += s[1];printf("%d\n", ans); } int main(){int t, i, j;scanf("%d", &t);while(t --){scanf("%d", &n);for(i = 0; i < n; i ++) scanf("%d", &s[i]);sort(s, s+n);if(n<3) printf("%d\n", s[n-1]);else solve();}return 0; }
題目鏈接：http://acm.nyist.net/JudgeOnline/problem.php?pid=47

版權聲明：本文博客原創文章。博客，未經同意，不得轉載。

總結

以上是生活随笔為你收集整理的nyoj 47 江 河问题 【贪婪】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。