Lomid1024

用户名：dotcpp0592448

访问量：1527

签　名：

有一种选择叫放弃

等　　级
排　　名	3439
经　　验	1929
参赛次数	2
文章发表	30
年　　龄	13
在职情况	学生
学　　校
专　　业

　　自我简介：

初中生

TA的其他文章

蓝桥杯算法提高VIP-和最大子序列，C++实现（DP）
浏览：13

蓝桥杯算法提高VIP-和最大子序列，C++实现（DP）
浏览：20

1051[编程入门]结构体之成绩统计 2，C++实现，一看就懂
浏览：51

你可能喜欢

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

1282: 公交汽车，c++代码实现，通俗易懂，超级详细

　　作者: Lomid1024　　　　发表时间：2023-08-22 21:04:24 浏览：167　|　评论：0　

原题链接：公交汽车

#1282: 公交汽车，c++代码实现
####题目描述：
[DOTCPP1282公交汽车](http://https://www.dotcpp.com/oj/problem1282.html "DOTCPP1282公交汽车")
####解题思路：
根据题目，乘客有无限的换乘机会，再通过仔细思考，我们发现，只有通过换乘才能使费用减小。

什么意思呢？

举个栗子：

乘坐1到10千米分别的价钱：

1 100000 200000 54 65 12 65 24 87 87

~~大傻逼~~大聪明（一个乘客）要乘坐2km的车，如果不换乘，就要消耗100000元（很合理吧），但大聪明通过仔细观察，经过九九七十一天的苦思冥想，经过成千上万次的科学计算，终于发现，只要通过一次换乘（第一次乘坐一千米，第二次也坐一千米），也就是说，大聪明乘坐2km的车只需要1+1=2元就够了（两次换乘，每次一千米，各一元）。

那么如果要乘坐3km呢？根据数据，要消耗200000元（也很合理）。但我们刚才已经算出，乘坐2km最需要2元，那么如果再乘坐1km，就只需要2+1=3元，而不是200000元了！

***现在我们开始写代码***

按照以上思路，我们定义一个数组`price[101]={0}`，用来装输入的价钱。
首先是输入，实现它很简单：
```cpp
	for(int i=1;i<=10;i++)
		cin>>price[i];
	cin>>n;
```
假设输入的数据是：

1 3 5 7 9 11 13 15 17 8
11

其中， 第一行十个整数分别表示行走1到10公里的费用

第二行一个整数n表示，旅客的总路程数。

现在`price`里的数据为（下标为1-11）

1 3 5 7 9 11 13 15 17 8 0

我们要一个个地处理每千米所要花费的最低价钱，用一个循环：
```cpp
for(int k=1k<=n;k++){
	尝试寻找k千米的最低价格
}
```
先看1km的价格，并没有办法使乘坐1km的价格减少，那么1km的最低价格已经被确定了，对吧。

好，现在`price`里的数据为（下标为1-11），黑体的数字为已经被确定的最低价格

****1**** 3 5 7 9 11 13 15 17 8 0

接下来看2km，尝试换成能否减低价格。我们发现只要动过一次换乘（第一第二次都乘坐1km，各一元），就只需要1+1=2元，比原价（3元）少。
说以，我们把乘坐2km的价格更新为2

****1 2**** 5 7 9 11 13 15 17 8 0

接下来看3km，尝试换成能否减低价格。我们发现只要动过一次换乘（第一乘坐1km，第二次乘坐2km，非别为1和2元），就只需要1+2=3元，比原价（5元）少。
说以，我们把乘坐3km的价格由5更新为3

****1 2 3**** 7 9 11 13 15 17 8 0

接下来看4km，尝试换成能否减低价格，我们发现，换乘的方法有：1km+3km和2km+2km。我们一个一个地尝试。
如果用1km+3km的方法，就只需要1+3=4元，比原价（7元）少。说以，我们把乘坐4km的价格由7更新为4。再来试一下1km+3km的方法，需要1+3=4元，并不比刚才的价格低，所以就不用更新了。

依此类推，当我们尝处理完9km时，`price`里的数据为（下标为1-11）

****1 2 3 4 5 6 7 8 9**** 8 0

当我们开始处理10km，发现如果只换成1次的话，有好几种换乘方法，但无论是哪一种，都无法使价格降低了，所以不用更新了。

现在，`price`里的数据为（下标为1-11）

****1 2 3 4 5 6 7 8 9 8**** 0

最后还有个11km的还没有处理。但题目说车最多只一次行驶10km，所以想要乘坐11km，就只能通过换乘（我们也可以理解为11km还没有标价）。我们第一个想到的是1km+10km，要9元，所以就把乘坐11km的价格更新为10元。
现在，`price`里的数据为（下标为1-11）

****1 2 3 4 5 6 7 8 9 8 9****

我们再来尝试2km+9km，3km+8km等方案。很显然，没有一种比9元少，所以就不用更新了。

现在，`price`里的数据为（下标为1-11）

****1 2 3 4 5 6 7 8 9 8 9****

这时，我们已经找到乘坐11km的最小花费，循环就结束了为11，也就是只需要求乘坐11km的最低价格）。

**根据我们完善刚才那个循环：**
完善前：
```cpp
for(int k=1;=n;k++){
	尝试寻找k千米的最低价格
}
```
完善后：
```cpp
for(int k=2;k<=n;k++){
	for(int i=1;i<=k;i++)//逐个寻找换乘方案
		if(price[k]>price[i]+price[k-i] || price[k]==0)//把k千米分解为i千米和（k-i）千米的换乘方案，把他的价钱和原价比较，如果比原价低或者还没有标价，就更新价格
			price[k]=price[i]+price[k-i];
}
```
瞬间高大上了，对不对？

最后是输出：
```cpp
cout<<price[n];
```
***好了！现在来看一下代码实现吧！***
####完整代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int main(){
	int price[101]={0},n;//别忘了吧price[101]全部置位0，这很重要
	for(int i=1;i<=10;i++)//输入
		cin>>price[i];
	cin>>n;
	for(int k=2;k<=n;k++){
		for(int i=1;i<=k;i++)
			if(price[k]>price[i]+price[k-i] || price[k]==0)//把k千米分解为i千米和（k-i）千米的换乘方案，把他的价钱和原价比较，如果比原价低或者还没有标价，就更新价格
				price[k]=price[i]+price[k-i];//更新价格
	}
	cout<<price[n];
	return 0;
}
```
####代码总结：
以上代码用了一种叫**动态规划**的算法（也许也可以理解为一种思路）。
但其实我自己也是一个动态规划的初学者，言辞可能使用不得当或思路有误（说真的，我自己的代码是否真的用了动然规划，我也不太清楚）。

但是我可以保证，我的代码提交到Dotcpp是正确的，我自己试过了。

最后，请各位大佬多多指教！

谢谢！

还有，如果这个篇文章对你有帮助的话，请给一个好评吧！~~我写这篇文章用了2小时！~~
谢谢！

还有！如发现文章错误，请在评论其下方提出来或私信作者，我会在第一时间修改。我自认为这边文章会错漏百出，因为我~~懒得检查~~语文水平不太好

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Lomid1024

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-统计字符（C++代码）

【密码】（C语言代码）

C二级辅导-等差数列（C语言代码）

1282: 公交汽车，c++代码实现，通俗易懂，超级详细

评论区

精彩推荐

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-求偶数和（C语言代码）

【数组的距离】（C语言代码）

WU-整数平均值（C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

Lomid1024

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-统计字符 （C++代码）

【密码】 （C语言代码）

C二级辅导-等差数列 （C语言代码）

1282: 公交汽车，c++代码实现，通俗易懂，超级详细

评论区

精彩推荐

Hello, world! （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-求偶数和 （C语言代码）

【数组的距离】 （C语言代码）

WU-整数平均值 （C++代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

C语言程序设计教程（第三版）课后习题9.10 （C语言代码）

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C二级辅导-统计字符（C++代码）

【密码】（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

C二级辅导-求偶数和（C语言代码）

【数组的距离】（C语言代码）

WU-整数平均值（C++代码）