def greedy(): n = 100 # 汽车满油后可行驶的最大距离 d = [50, 80, 39, 60, 40, 32] # 加油站的距离 k = len(d) # 加油站的数量 # 检查是否有加油站距离超过汽车的最大行驶距离 for dist in d: if dist > n: print('no solution') return num = 0 # 加油次数 current_position = 0 # 当前行驶的距离 # 遍历加油站列表 for i in range(k): # 如果当前位置加上下一个加油站的距离超过了汽车的最大行驶距离,则需要在当前加油站加油 if current_position + d[i] > n: num += 1 # 加油次数加一 current_position = d[i] # 更新当前位置为当前加油站的距离 else: current_position += d[i] # 更新当前位置 print("总共加油次数:", num) if __name__ == '__main__': greedy() 输出结果:
相关文章
- 11-19算法--“汽车加油”问题.
- 11-19蓝桥杯c++算法学习【1】之枚举与模拟(卡片、回文日期、赢球票、既约分数:::非常典型的比刷例题!!!)- 对于一个8位数的整型日期,可以通过除法和取余运算来获取它的每一位数字。比如: 若整数date 的值为20050511,它从高到低的每一数位上的数可以通过下列方法得到。 • data / 10000000 = 2; • data / 1000000 % 10 = 0; • data / 100000 % 10 = 0; • data / 10000 % 10 = 5; • data / 1000 % 10 = 0; • data / 100 % 10 = 5; • data / 10 % 10 = 1; • data % 10 = 1。 对于本题,若用a[1]、a[2]、a[3]、a[4]、a[5]、a[6]、a[7]、a[8] 分别存储每一位,则一个 回文日期须满足: 一个ABABBABA 型回文日期须满足以下条件。 a[1] = a[3] = a[6] = a[8];a[2] = a[4] = a[5] = a[7]. 对于一个日期字符串,可以直接通过下标来获取它的每一位数字。例如,string date = “20050511”,它从高到低的每一位分别可以通过data[0],data[1],...,data[7] 得到。判断回文日期及ABABBABA型回文日期的方式和上述方法类似。 不难看出,字符串获取日期的每一位数字是要比整型简单的,所以在判断回文日期及 ABABBABA 型回文日期时可以将整型转换为字符串来操作,如参考代码所示。 #include <bits/stdc++.h> using namespace std; int date = 20050511; string s = to_string(date); // 将整型转换为字符串, s = "20050511" // 判断回文日期 bool check1(int date) { string s = to_string(date); if (s[0] == s[7] && s[1] == s[6] && s[2] == s[5] && s[3] == s[4]) return true; return false; } // 判断 ABABBABA 型回文日期 bool check2(int date) { string s = to_string(date); if (s[0] == s[2] && s[0] == s[5] && s[0] == s[7] && s[1] == s[3] && s[1] == s[4] && s[1] == s[6]) return true; return false; } 2. 如何枚举日期 对于一个整型日期,可以用最简单的方式枚举,即令该日期不断+1,直到出现满足ABAB BABA 型的回文日期。 但这样存在一个问题:会枚举出许多不合法的日期(如20209999)。为此,我们需要对 日期进行合法性判断:设y,m,d分别表示年、月、日,month[i]表示第i个月的天数,那么当m12或dmonth[m]时日期不合法,反之日期合法,如参考代码所示。 #include <iostream> #include <string> using namespace std; int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool check(int date) { string s = to_string(date); //stoi->将字符串转为整型 int y = stoi(s.substr(0, 4)), m = stoi(s.substr(4, 2)), d = stoi(s.substr(6, 2)); if (y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) month[2] = 29; else month[2] = 28; if (m < 1 || m > 12 || d < 1 || d > month[m]) return false; return true; } int main { int date = 20050511; for (int i = date + 1;; i++) { if (!check(i)) continue; // 找到下一个有效日期后,可以在这里进行进一步处理 // 例如,检查是否是回文日期或 ABABBABA 型回文日期 cout << "Next valid date: " << i << endl; break; } return 0; } 不过这样的枚举量是相当大的,要在比赛中完成本题要求的所有测试数据不太现实。 那么,还有什么枚举方法呢? 可以直接枚举合法日期。枚举合法日期只需模拟日期的变化规律即可,对应参考代码如 下所示。 #include <iostream> using namespace std; int month[13] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int main { int date = 20050511; int y = date / 10000, m = date / 100 % 100, d = date % 100; for (int i = y;; i++) { if (i % 400 == 0 || (i % 100 != 0 && i % 4 == 0)) month[2] = 29; // 闰年2月有29天 else month[2] = 28; int j = (i == y) ? m : 1; // 如果是i = y,则月份从m开始枚举,否则从1开始枚举 for (; j <= 12; j++) { int k = (i == y && j == m) ? d : 1; // 如果i = y并且j = m,则日从d开始枚举,否则从1开始枚举 for (; k <= month[j]; k++) { int new_date = i * 10000 + j * 100 + k; // 在这里可以进行进一步处理,例如检查是否是回文日期或ABABBABA型回文日期 cout << "Next valid date: " << new_date << endl; return 0; // 找到第一个有效日期后退出程序 } } } return 0; } 综上 :
- 11-19贪心算法-汽车加油
- 11-19【汽车租聘管理与推荐】Python+Django网页界面+推荐算法+管理系统网站
- 11-19数据结构和算法-01背包问题01-认识01背包
- 11-19Matlab实现白鲸优化算法(BWO)求解路径规划问题
- 11-19Matlab实现粒子群优化算法(PSO)求解路径规划问题
- 11-19代码随想录算法训练营第46期Day37,38,39,41-而m 和 n相当于是一个背包,两个维度的背包。 理解成多重背包的同学主要是把m和n混淆为物品了,感觉这是不同数量的物品,所以以为是多重背包。 但本题其实是01背包问题! 只不过这个背包有两个维度,一个是m 一个是n,而不同长度的字符串就是不同大小的待装物品。 开始动规五部曲: 确定dp数组(dp table)以及下标的含义 dp[i][j]:最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。 确定递推公式 dp[i][j] 可以由前一个strs里的字符串推导出来,strs里的字符串有zeroNum个0,oneNum个1。 dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。 然后我们在遍历的过程中,取dp[i][j]的最大值。 所以递推公式:dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1); 此时大家可以回想一下01背包的递推公式:dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); 对比一下就会发现,字符串的zeroNum和oneNum相当于物品的重量(weight[i]),字符串本身的个数相当于物品的价值(value[i])。 这就是一个典型的01背包! 只不过物品的重量有了两个维度而已。 dp数组如何初始化 01背包的dp数组初始化为0就可以。 因为物品价值不会是负数,初始为0,保证递推的时候dp[i][j]不会被初始值覆盖。 确定遍历顺序 01背包一定是外层for循环遍历物品,内层for循环遍历背包容量 那么本题也是,物品就是strs里的字符串,背包容量就是题目描述中的m和n。(相当于之前的一维dp,采用了滚动数组) 倒序遍历是为了保证物品i只被放入一次!。但如果一旦正序遍历了,那么物品0就会被重复加入多次! 那么问题又来了,为什么二维dp数组遍历的时候不用倒序呢?
- 11-19滤波算法与SLAM:从概率角度理解SLAM问题
- 11-19最短路问题之dijikstra算法