【題目描述】

　　　　小S新買了一個掌上游戲機，這個游戲機由兩節(jié)5號電池供電。為了保證能夠長時間玩游戲，他買了很多5號電池，這些電池的生產(chǎn)商不同，質(zhì)量也有差異，因而使用壽命也有所不同，有的能使用5個小時，有的可能就只能使用3個小時?，F(xiàn)在已知電池的數(shù)量和電池能夠使用的時間，請你找一種方案使得使用時間盡可能的長。

【題目鏈接】

　　　　http://noi.openjudge.cn/ch0406/2469/

【算法】

　　　　其實一開始想的也沒錯：所有電池按使用時間之和分成盡可能接近的兩組，若其中一組只有一個數(shù)，則最長時間為另一組使用時間之和，若兩組均超過一個，則說明一定能全用完。事實上，兩組均超過一個換句話說就是，所有電池中能用時間最大的那個小于總時間的一半，不然就會自成一組。。。所以這題目可以貪心的考慮最大時長電池，若大于其它所有電池之和，則為其余電池之和，反之為總時長一半。

【代碼】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,sum,maxn,i,a;
 4 int main()
 5 {
 6     while(scanf("%d",&n)!=EOF) {
 7         sum=maxn=0;
 8         for(i=1;i<=n;i++) scanf("%d",&a),sum+=a,maxn=max(maxn,a);
 9         if(maxn>sum-maxn) printf("%.1f
",(double)sum-maxn);
10         else printf("%.1f
",sum/2.0);
11     }
12     return 0;
13 }

總結(jié)

以上是生活随笔為你收集整理的电池寿命问题 （贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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