贪心算法4（c++）
过河的最短时间
题目描述
输入
在漆黑的夜里，N位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话，大家是无论如何也不敢过桥去的。不幸的是，N个人一共只带了一只手电筒，而桥窄得只够让两个人同时过，如果各自单独过桥的话，N人所需要的时间已知:而如果两人同时过桥，所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是，如何设计一个方案，让这N人尽快过桥，计算成绩这N个人的最短过桥时间。
每组测试数据的第一行是一个整数N(1<=N<=1000)表示共有N个人要过河
每组测试数据的第二行是N个整数Si,表示这N个人过河所需要花时间。(0<Si<=100)
输出
比如:有四个人甲乙丙丁，他们过河需要的时间分别为，甲:1乙:2丙:5所有人过河的最短时间悶Ž閨辰:10第一种办法:最快的2个人先过桥，然后让跑的最快的人来回去接剩下的人:先让甲乙过去(2分钟)，甲回来(1分钟)，甲丙过去(5分钟)，甲回来(1分钟)，甲丁再过去(10分钟)，总共需要19分钟就可以让四个人都过去。第二种办法:让最慢的地2个人一起过桥，减少最慢的人在桥上的次数先让甲乙过去(2分钟)，甲回来(1分钟)，丙丁过去(10分钟)，乙回来(2分钟)，甲乙再过去(2分钟)总共需要17分钟可以让四个人都过去。。那么最慢的时间就是需要17分钟!
样例
输入复制
4
1 2 5 10
输出复制
17
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{int n;cin>>n;int a[1010] = {0};for(int i = 0;i<n;i++){cin>>a[i];}sort(a+0,a+n);int k1 = n-2;int k2 = n-1;int t = a[1];while(true){int t1 = a[0]+a[k2]+a[1]+a[1];int t2 = a[0]+a[k2]+a[0]+a[k1];if(t1<t2) t = t+t1;else t = t+t2;k1--;k1--;k2--;k2--;if(k1==0||k1==1) break;}if(k1==1) t = t+a[0]+a[3];cout<<t;return 0;
}特殊密码锁
描述有一种特殊的二进制密码锁，由n个相连的按钮组成(n<30)，按钮有凹/凸两种状态，用手按按钮会改变其状态。然而让人头疼的是，当你按一个按钮时，跟它相邻的两个按钮状态也会反转。当然，如果你按的是最左或者最右边的按钮，该按钮只会影响到跟它相邻的一个按钮。
当前密码锁状态已知，需要解决的问题是，你至少需要按多少次按钮，才能将密码锁转变为所期望的目标状态,
输入
两行，给出两个由0、1组成的等长字符串，表示当前/目标密码锁状态，其中0代表凹，1代表凸。输出
至少需要进行的按按钮操作次数，如果无法实现转变，则输出impossible
样例输入
011
000
样例输出
1
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{string a,b;cin>>a>>b;int cnt = 0;for(int j = 0;j<10;j++){for(int i = 0;i<a.size();i++){if(a==b){cout<<cnt;return 0;}if(a[i]!=b[i]){if(i==0&&a[0]!=b[0]&&a[1]!=b[1]&&a[2]==b[2]){cnt++;a[0] = b[0];a[1] = b[1];i = i+2;}else if(i==0&&a[0]!=b[0]&&a[1]!=b[1]&&a[2]!=b[2]){cnt++;a[0] = b[0];a[1] = b[1];a[2] = b[2];i = i+3;}else{int ii = i+1;if(ii<a.size()){int i2 = (int)(a[ii]-48);i2 = (i2+1)%2;a[ii] = (char)(i2+48);}if(ii<a.size()){int i3 = (int)(a[ii+1]-48);i3 = (i3+1)%2;a[ii+1] = (char)(i3+48);}if(ii>=0){int i1 = (int)(a[ii-1]-48);i1 = (i1+1)%2;a[ii-1] = (char)(i1+48);}cnt++;}}}}cout<<"impossible";return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main()
{int n,m;cin>>n>>m;int a[1010] = {0};for(int i = 0;i<n;i++){cin>>a[i];}if(n<=m){cout<<a[n-1];return 0;}int b[1010] = {0};for(int i = 0;i<m;i++){b[i] = a[i];}for(int i = m;i<n;i++){sort(b+0,b+m);b[0] = b[0]+a[i];}sort(b+0,b+n);cout<<b[n-1];return 0;
}