題意：有一個(gè)橋，每次只能兩個(gè)人拿著手電筒通過然后一個(gè)人拿著電筒回來(lái)，然后讓新人過去，給出每個(gè)人的過橋時(shí)間，問最后總的最小時(shí)間。

思路：貪心。1個(gè)人2個(gè)人好考慮，排好序，三個(gè)人是13，1，12，大于3個(gè)人的時(shí)候，考慮2i，2，12和1i，1，1i-1的最小值，然后不停－2直到得到可求的范圍。

code：

#include <bits/stdc++.h> using namespace std;const int M=1005; int T,n,v[M]; int main() {scanf("%d",&T);while (T--){scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",v+i);sort (v+1,v+1+n);if (n==1){printf("%d\n%d\n",v[1],v[1]);}else if (n==2){printf("%d\n%d %d\n",v[2],v[1],v[2]);}else {int ans=v[2];for (int i=n;i>=4;i-=2)ans+=min(v[2]*2+v[1]+v[i],2*v[1]+v[i]+v[i-1]);if (n&1) ans+=v[3]+v[1];printf("%d\n",ans);for (int i=n;i>=4;i-=2){if (v[2]*2+v[1]+v[i]<2*v[1]+v[i]+v[i-1])printf("%d %d\n%d\n%d %d\n%d\n",v[1],v[2],v[1],v[i-1],v[i],v[2]);else printf("%d %d\n%d\n%d %d\n%d\n",v[1],v[i],v[1],v[1],v[i-1],v[1]);}if (n&1) printf("%d %d\n%d\n",v[1],v[3],v[1]);printf("%d %d\n",v[1],v[2]);}if (T) puts("");} }

總結(jié)

以上是生活随笔為你收集整理的uva 10037——Bridge的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。