一本通1229 电池的寿命（贪心 转换思维)

1229：电池的寿命
提交数: 3346 通过数: 1834
【题目描述】
小S新买了一个掌上游戏机，这个游戏机由两节5号电池供电。为了保证能够长时间玩游戏，他买了很多5号电池，这些电池的生产商不同，质量也有差异，因而使用寿命也有所不同，有的能使用5个小时，有的可能就只能使用3个小时。显然如果他只有两个电池一个能用5小时一个能用3小时，那么他只能玩3个小时的游戏，有一个电池剩下的电量无法使用，但是如果他有更多的电池，就可以更加充分地利用它们，比如他有三个电池分别能用3、3、5小时，他可以先使用两节能用3个小时的电池，使用半个小时后再把其中一个换成能使用5个小时的电池，两个半小时后再把剩下的一节电池换成刚才换下的电池（那个电池还能用2.5个小时），这样总共就可以使用5.5个小时，没有一点浪费。
现在已知电池的数量和电池能够使用的时间，请你找一种方案使得使用时间尽可能的长。

【输入】
输入包含多组数据。每组数据包括两行，第一行是一个整数N(2≤N≤1000)，表示电池的数目，接下来一行是N个正整数表示电池能使用的时间。
【输出】
对每组数据输出一行，表示电池能使用的时间，保留到小数点后1位。
【输入样例】
2
3 5
3
3 3 5

【输出样例】
3.0
5.5

解析：
本道题目使用贪心算法。

个人思路 一（超时 不能通过 只是一种想法）：
用a数组记录每个电池的寿命。
我一开始想的是每次寻找寿命的最大值和次大值。（可以通过每次排序，但是时间复杂度很高）每次都将最大值和次大值减去0.5。（因为0.5是每个电池的因数）直到找到的次大值为0为止。——这样的目的在于尽量保留较多的电池数量，所以每次使用的都是大剩余寿命的电池。

思路 二：
换种方式，从结果考虑入手。
求一下所有电池的寿命和sum。
如果sum（和）- max（最大值）<=max，就说明其他的电池都消耗完毕也不能（或正好）抵消max的寿命，那么结果就是小电池寿命和的极限，即sum-max。
如果sum（和）- max（最大值）>max，就说明n的值一定>=3.（只有三个及其以上才能出现这种情况），在这种情况下，电池是可以中途互换的，所以每个电池都可以是0.5小时的整数、偶数倍。对于这些偶数，一定可以协调起来（可以看做每次消耗两个不同电池的0.5)，让所有的电池都正好耗尽。所以结果为sum/2;

代码：
思路一（超时代码 不能过哦)

#include
#include
#include
using namespace std;//思路：公约数 半个小时。 
//尽量选取两个较大的数的半个小时，保证有更多的没有用完的电池 double r[1001];
double a[1001]; 
int m_sort(int s,int t)//归并排序
{if(s==t)return 0;int mid=(s+t)/2;m_sort(s,mid);m_sort(mid+1,t);int i=s,j=mid+1,k=s;while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[i];k++;i++;}else{r[k]=a[j];k++;j++;}}while(i<=mid){r[k]=a[i];k++;i++;}while(j<=t){r[k]=a[j];k++;j++;}for(int i=s;i<=t;i++)a[i]=r[i];
}int main()
{int n;int nm=0;//记录可以用几个半个小时 int max_z,max_ci; while(scanf("%d",&n)!=EOF){nm=0; for(int i=1;i<=n;i++){cin>>a[i];}a[0]=0;m_sort(1,n);//排序 max_z=n;max_ci=n-1;//每次找最大和次大的两个值 while(a[max_ci]!=0)//直到第二大的那个为0 ，就剩1节电池或者没有电池了为止 {nm++;a[max_z]=a[max_z]-0.5;a[max_ci]=a[max_ci]-0.5;max_z=max_ci=0;//每次的初始化 for(int i=1;i<=n;i++)//先找最大值 {if(a[i]>a[max_z])max_z=i;}for(int i=1;i<=n;i++)//再找次大值 {if(a[i]>a[max_ci]&&max_z!=i)max_ci=i; }}printf("%.1f\n",(float)nm/2);}return 0;} 

思路二（可以通过）：

#include
#include
#include
using namespace std;
//思路：
//求一下sum总和，如果sum减去最大值小于最大值max就说明没有什么组合可以更大的抵消最大值，结果就是其他值轮番消耗最大值,小电池的和的极限，即sum-max。 
//第二种情况是sum减去最大值大于了大值，这种情况的结果是sum的一半。因为这样n一定会>=3,当>=3时就可以出现换电池的情况，因为每一个电池都是0.5的偶数倍，所以一定可以协调全部用完 
double r[1001];
double a[1001]; 
int m_sort(int s,int t)//归并排个序 
{if(s==t)return 0;int mid=(s+t)/2;m_sort(s,mid);m_sort(mid+1,t);int i=s,j=mid+1,k=s;while(i<=mid&&j<=t){if(a[i]<=a[j]){r[k]=a[i];k++;i++;}else{r[k]=a[j];k++;j++;}}while(i<=mid){r[k]=a[i];k++;i++;}while(j<=t){r[k]=a[j];k++;j++;}for(int i=s;i<=t;i++)a[i]=r[i];
}int main()
{int n;double sum=0;while(cin>>n){sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];//求和 }// cout<m_sort(1,n);//排一下序double max_s=a[n];//求出最大值 if(sum-max_s<=max_s)//第一种 printf("%.1lf\n",sum-max_s);else if(sum-max_s>max_s)//第二种 printf("%.1lf\n",sum/2);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！