uvalive 2949 - Elevator Stopping Plan(贪心+二分)

2024-06-05 05:08

本文主要是介绍uvalive 2949 - Elevator Stopping Plan(贪心+二分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目连接:2949 - Elevator Stopping Plan


题目大意:某个抠门的公司只有一个电梯, 现在有n 个人从1楼, 他们有各自想要到达的楼层, 然后电梯每上一楼需要4 秒, 每在一个楼层开门需要10 秒, 然后然爬楼梯的话需要20一楼。问, 如何用最短的时间让所有人都到达各自想要到的楼层。


解题思路:因为人可以爬楼梯, 所以可以在某个楼层下楼之后走楼梯到达想要到的楼层, 只要在最后一个人到达之前就可以。 对于时间可以采取二分的方式搜索, 所以只要判断某个时间能否将所有人送到指定楼层就可以了。 对于判断我们可以用贪心去做, 尽量让电梯停在较高的楼层,只要剩余的时间够使得人走到自己的楼层就可以了。


#include <stdio.h>
#include <string.h>
const int N 

这篇关于uvalive 2949 - Elevator Stopping Plan(贪心+二分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1032150

相关文章

二分查找(算法篇)

算法之二分查找 二分查找 概念: 针对于已经预先排序好的数据,每次将数据进行对半查找,然后看它中间的数据是否是要找的,如果是就返回中间位置,不是就判断该数据是在前半部分还是后半部,然后在进而取其中部,看其是否找到,然后如果还没找到就一直重复操作,直到找到为止,该算法时间复杂度为O(logn) 代码: int search(vector<int>& nums, int target) {i

C语言实现简单二分搜索和四个变体问题

二分查找 简单的二分查找 简单指的是在不存在重复元素的数组中,查找值等于给定值的情况。 int bsearch(int *arr, int n, int value){int low = 0;int high = n - 1;int mid;while (low <= high){mid = low + ((high-low) >> 1);if (arr[mid] == value){re

贪心推公式——AcWing 125. 耍杂技的牛

贪心推公式 定义 贪心算法是一种在每一步选择中都采取在当前状态下最优的选择,希望通过局部的最优选择来得到全局最优解的算法策略。 运用情况 问题具有最优子结构,即一个问题的最优解包含其子问题的最优解。可以通过局部最优决策逐步推导到全局最优。问题的选择策略相对明确且易于计算。 注意事项 贪心算法并不总是能得到全局最优解,可能会陷入局部最优。对于一些复杂问题,需要谨慎验证其正确性。可能需要对

leetcode 二分查找·系统掌握 x的平方根

题目: 题解 这题可以使用~01~泛型查找在0~x/2的范围内查找答案。 int mySqrt(int x) {long l=0,r=x,mid;while(l<r){mid=(l+r+1)>>1;if(mid*mid>x)r=mid-1;else l=mid;}//因为一定有答案所以不用判定是否查找失败return l;}

leetcode 二分查找·系统掌握 第一个错误版本

题意: 题解: 就是经典的~01~泛型查找,而且一定存在这样错误的版本所以查找不会"失败",返回每次查找结果即可。 int firstBadVersion(int n) {long l=1,r=n,mid;while(l<r){mid=(l+r)>>1;if(isBadVersion(mid))r=mid;else l=mid+1;}return l;}

leetcode 二分查找·系统掌握 搜索二维矩阵

题目: 题解: 一个可行的思路是使用~01~泛型对每一行的最后一个元素进行查找找到第一个大于等于target的那一行,判断查找结果如果“失败”返回false否则继续在改行进行常规二分查找target的值根据查找结果返回即可。 bool searchMatrix(vector<vector<int>>& matrix, int target) {int l=0,r=matrix.size()-

微策略面试题:在旋转后的数组中查找元素(二分查找)

版权所有。所有权利保留。 欢迎转载,转载时请注明出处: http://blog.csdn.net/xiaofei_it/article/details/17123303 一个无重复元素的有序数组,经过若干次旋转后,得到一个新数组。比如[1,4,5,8,10,12,56,78]变成[12,56,78,1,4,5,8,10]。 现在要在这个数组中寻找元素。 其实算法很简单,就是用二分

素数伴侣--最大二分匹配

#include<bits/stdc++.h>using namespace std;#define N 100int edge[N][N],cx[N],cy[N];//edge记录两点的关系,如果两点相连,则edge【i】【j】为1int visited[N];//判断该店是否被访问过int nx,ny,res;const int M=60000+100;bool prim[M];

代码随想录第31天|贪心算法

134. 加油站 参考 思路: 以每个油站相差作为判断, 比如: gas [5 8 2 8]cost [6 5 6 6] [-1 3 -4 2] 错误 : 把相差最大点当作起点判断能否绕一圈 : 相加数组是否小于0局部最优: 当前累加rest[i]的和curSum一旦小于0,起始位置至少要是i+1,因为从i之前开始一定不行全局最优: 找到可以跑一圈的起始位置 class

【秋招刷题打卡】Day02-二分系列之-二分查找

Day02-二分系列之-二分查找 前言 给大家推荐一下咱们的 陪伴打卡小屋 知识星球啦,详细介绍 =>笔试刷题陪伴小屋-打卡赢价值丰厚奖励 <= ⏰小屋将在每日上午发放打卡题目,包括: 一道该算法的模版题 (主要以力扣,牛客,acwing等其他OJ网站的题目作为模版)一道该算法的应用题(主要以往期互联网大厂 笔试真题 的形式出现,评测在咱们的 笔试突围OJ) 小屋day02 我们预