過河的最短時間
題目描述
輸入
在漆黑的夜里，N位旅行者來到了一座狹窄而且沒有護欄的橋邊。如果不借助手電筒的話，大家是無論如何也不敢過橋去的。不幸的是，N個人一共只帶了一只手電筒，而橋窄得只夠讓兩個人同時過，如果各自單獨過橋的話，N人所需要的時間已知:而如果兩人同時過橋，所需要的時間就是走得比較慢的那個人單獨行動時所需的時間。問題是，如何設(shè)計一個方案，讓這N人盡快過橋，計算成績這N個人的最短過橋時間。
每組測試數(shù)據(jù)的第一行是一個整數(shù)N(1<=N<=1000)表示共有N個人要過河
每組測試數(shù)據(jù)的第二行是N個整數(shù)Si,表示這N個人過河所需要花時間。(0<Si<=100)
輸出
比如:有四個人甲乙丙丁，他們過河需要的時間分別為，甲:1乙:2丙:5所有人過河的最短時間悶?閨辰:10第一種辦法:最快的2個人先過橋，然后讓跑的最快的人來回去接剩下的人:先讓甲乙過去(2分鐘)，甲回來(1分鐘)，甲丙過去(5分鐘)，甲回來(1分鐘)，甲丁再過去(10分鐘)，總共需要19分鐘就可以讓四個人都過去。第二種辦法:讓最慢的地2個人一起過橋，減少最慢的人在橋上的次數(shù)先讓甲乙過去(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)，按鈕有凹/凸兩種狀態(tài)，用手按按鈕會改變其狀態(tài)。然而讓人頭疼的是，當你按一個按鈕時，跟它相鄰的兩個按鈕狀態(tài)也會反轉(zhuǎn)。當然，如果你按的是最左或者最右邊的按鈕，該按鈕只會影響到跟它相鄰的一個按鈕。
當前密碼鎖狀態(tài)已知，需要解決的問題是，你至少需要按多少次按鈕，才能將密碼鎖轉(zhuǎn)變?yōu)樗谕哪繕藸顟B(tài),
輸入
兩行，給出兩個由0、1組成的等長字符串，表示當前/目標密碼鎖狀態(tài)，其中0代表凹，1代表凸。輸出
至少需要進行的按按鈕操作次數(shù)，如果無法實現(xiàn)轉(zhuǎn)變，則輸出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;
}