电池的寿命
描述 小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
思路：
分两种情况，一种是其中一个电池的电量大于其他电池电量之和，那这个电池可以和其他所有电池配合使用，使用总时间为其他电池的电量之和。另一种情况是最大电量的电池电量比其他所有电池电量之和小，它们总是可以配合使用将电量全部用完的，使用总时间为这些电池的总电量的一半。
题解（贪心）：
#include<iostream>#include<cstdio>using namespace std;int main(){ int n; while(scanf("%d",&n)!=EOF) { double sum=0; double maxn=0; for(int i=1;i<=n;i++) { double x; scanf("%lf",&x); maxn=max(maxn,x); sum+=x; } sum-=maxn; if(sum<=maxn) { PRintf("%.1lf/n",sum); } else { printf("%.1lf/n",(maxn+sum)/2.0); } } return 0;}———————————————我是华丽的分割线——————————————————-
特殊密码锁
描述 有一种特殊的二进制密码锁，由n个相连的按钮组成（n<30），按钮有凹/凸两种状态，用手按按钮会改变其状态。
然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态。
输入 两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。 输出 至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible。 样例输入 011 000 样例输出 1
思路：
因为每次按按钮都会改变当前位置和两边的数字，我们可以考虑从你需要改变的那个数字的后一位开始按，那么你改变的序列前面不会改变，改变的只会是你后面的按钮，这样一直到最后判断序列能否匹配就行了。（ps：第一个按钮按不按对结果会有影响，所以要分按第一个按钮和不按第一个按钮两种情况取最小值）
题解（贪心）：
#include<iostream>#include<cstdio>using namespace std;string x,y,s;int n;void change1(int i){ x[i]^=1; x[i-1]^=1; if(i+1<n) { x[i+1]^=1; }}void change2(int i){ s[i]^=1; s[i-1]^=1; if(i+1<n) { s[i+1]^=1; }}int main(){ int ans1=0,ans2=1; cin>>x>>y; s=x; n=x.length(); for(int i=1;i<n;i++) { if(x[i-1]!=y[i-1]) { ans1++; change1(i); } } s[0]^=1; s[1]^=1; for(int i=1;i<n;i++) { if(s[i-1]!=y[i-1]) { ans2++; change2(i); } } if(x==y||s==y) { printf("%d",min(ans1,ans2)); } else { printf("impossible"); } return 0;}新闻热点
疑难解答
