文章目錄
- 前言：
- 題目：
- 思路：
- 見題目：
- 思路：
- 程式
- 全部程式(以多組輸入定義main函式)
- 效果圖
前言：
| 1.博主實力有限，有什么錯誤地方，請你斧正！謝謝！ |
|---|
2.思維題真的真的讓人頭大 ,但卻有意思，0.0. |
題目：
| 有N（N>=2）個人過橋，只有一把手電筒，每個人過橋速度（分鐘）由鍵盤輸入，如過2人過橋，時間為速度最慢的那個，問N個人過完橋需要的最短時間， |
|---|
思路：
| 1.時間最短，必然傳遞手電筒的時間最短，因此需要將速度最快的2人做為傳手電筒的人選， |
|---|
| # 前言： |
| 1.博主實力有限，有什么錯誤地方，請你斧正！謝謝！ |
|---|
2.思維題真的真的讓人頭大 |
見題目：
| 有N（N>=2）個人過橋，只有一把手電筒，每個人過橋速度（分鐘）由鍵盤輸入，如過2人過橋，時間為速度最慢的那個，問N個人過完橋需要的最短時間， |
|---|
思路：
| 1.時間最短，必然傳遞手電筒的時間最短，因此需要將速度最快的2人做為傳手電筒的人選， |
|---|
2…考慮到手電筒的要求，我們必須讓速度快的在速度慢的之前到達對岸，這樣不僅橋上時間可以減斷，而且當速度慢的到了后，可以讓速度快的傳送手電筒， |
3.實際情況;速度最快和次快的2人先走，回來一個速度最快的，然后速度最慢的2人過去,速度次快的人回來.然后回圈，這樣在速度最快和次快的2人的配合下，極大的減短，不用考慮中間速度的使用， |
| 4.每次回圈相當于送過去2人 |
| 5.最后剩3人，和2人的特殊情況，要區分， |
程式
void order_board(int *p,int n)//選擇法排序，從小到大，
{
int i = 0;
int j = 0;
int min = 0;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
if (p[j] < p[min])min = j;//遍歷找到陣列最小的下標，
}
if (min != i)//選出的下標不為i就交換
{
int tmp = p[i];
p[i] = p[min];
p[min] = tmp;
}
}
}
int max_peo(int* p, int n)//選擇出最長的時間，并在陣列中將其重值為0.
{
int i = 0;
int max = 0;
for (i = 0; i < n; i++)
{
if (p[i] > p[max])max = i;
}
int tmp = p[max];
p[max] = 0;
return tmp;
}
void fun(int* p, int n)
{
int tmp = n;//每次回圈相當于送過去2人.
int max_max = 0;//用于選出的最慢的人
int max_min = 0;//用于選出的次慢的人.
int max1 = p[0];//速度最快的人
int max2 = p[1];//速度次快的人
int Time = 0;
while (1)
{
max_max = max_peo(p,n); //選出的最慢的人
max_min = max_peo(p, n); //選出的次慢的人
if (tmp>3)
{
Time = Time + max2 + max1 + max_max + max2;
tmp-=2;
}
else if (tmp==3)//最后只剩3人的特殊情況
{
Time =Time+ max1 + max_max + max_min;
break;
}
else if (tmp == 2)//最后只剩2人的特殊情況
{
Time = Time + max2;
break;
}
}
printf("所需時間為：%d\n", Time);
}
全部程式(以多組輸入定義main函式)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
void order_board(int *p,int n)//選擇法排序，從小到大，
{
int i = 0;
int j = 0;
int min = 0;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
if (p[j] < p[min])min = j;//遍歷找到陣列最小的下標，
}
if (min != i)//選出的下標不為i就交換
{
int tmp = p[i];
p[i] = p[min];
p[min] = tmp;
}
}
}
int max_peo(int* p, int n)//選擇出最長的時間，并在陣列中將其重值為0.
{
int i = 0;
int max = 0;
for (i = 0; i < n; i++)
{
if (p[i] > p[max])max = i;
}
int tmp = p[max];
p[max] = 0;
return tmp;
}
void fun(int* p, int n)
{
int tmp = n;
int max_max = 0;//用于選出的最慢的人
int max_min = 0;//用于選出的次慢的人.
int max1 = p[0];//速度最快的人
int max2 = p[1];//速度次快的人
int Time = 0;//每次回圈相當于送過去2人.
while (1)
{
max_max = max_peo(p,n); //選出的最慢的人
max_min = max_peo(p, n); //選出的次慢的人
if (tmp>3)
{
Time = Time + max2 + max1 + max_max + max2;
tmp-=2;
}
else if (tmp==3)//最后只剩3人的特殊情況
{
Time =Time+ max1 + max_max + max_min;
break;
}
else if (tmp == 2)//最后只剩2人的特殊情況
{
Time = Time + max2;
break;
}
}
printf("所需時間為：%d\n", Time);
}
int main ()
{
int peo[100] = { 0};
int i = 0;
while (~scanf("%d", &peo[i++]))
{
if(getchar() == '\n')
{
int sz = i;
order_board(peo, sz);
fun(peo, sz);
i = 0;//每次都可以重新賦值陣列，
}
}
return 0;
}
效果圖
