首页 > 编程语言 >算法校赛准备

算法校赛准备

时间:2024-10-09 23:13:34浏览次数:8  
标签:独木桥 int 整数 算法 坐标 士兵 准备 校赛 初始

独木桥

题目背景

战争已经进入到紧要时间。你是运输小队长,正在率领运输部队向前线运送物资。运输任务像做题一样的无聊。你希望找些刺激,于是命令你的士兵们到前方的一座独木桥上欣赏风景,而你留在桥下欣赏士兵们。士兵们十分愤怒,因为这座独木桥十分狭窄,只能容纳 $1$ 个人通过。假如有 $2$ 个人相向而行在桥上相遇,那么他们 $2$ 个人将无法绕过对方,只能有 $1$ 个人回头下桥,让另一个人先通过。但是,可以有多个人同时呆在同一个位置。

题目描述

突然,你收到从指挥部发来的信息,敌军的轰炸机正朝着你所在的独木桥飞来!为了安全,你的部队必须撤下独木桥。独木桥的长度为 $L$,士兵们只能呆在坐标为整数的地方。所有士兵的速度都为 $1$,但一个士兵某一时刻来到了坐标为 $0$ 或 $L+1$ 的位置,他就离开了独木桥。

每个士兵都有一个初始面对的方向,他们会以匀速朝着这个方向行走,中途不会自己改变方向。但是,如果两个士兵面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。

由于先前的愤怒,你已不能控制你的士兵。甚至,你连每个士兵初始面对的方向都不知道。因此,你想要知道你的部队最少需要多少时间就可能全部撤离独木桥。另外,总部也在安排阻拦敌人的进攻,因此你还需要知道你的部队最多需要多少时间才能全部撤离独木桥。

输入格式

第一行共一个整数 $L$,表示独木桥的长度。桥上的坐标为 $1, 2, \cdots, L$。

第二行共一个整数 $N$,表示初始时留在桥上的士兵数目。

第三行共有 $N$ 个整数,分别表示每个士兵的初始坐标。

输出格式

共一行,输出 $2$ 个整数,分别表示部队撤离独木桥的最小时间和最大时间。$2$ 个整数由一个空格符分开。

样例 #1

样例输入 #1

4
2
1 3

样例输出 #1

2 4

提示

对于 $100%$ 的数据,满足初始时,没有两个士兵同在一个坐标,$1\le L\le5\times 10^3$,$0\le N\le5\times10^3$,且数据保证 $N\le L$。

代码

点击查看代码
#include<iostream>
using namespace std;
const int MAX = 5010;
int p[MAX] ;//位置
void MySwap(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}
int main() {
	int L;//独木桥长度
	int n;//人数
	int min;
	int mintime=0,maxtime=0;
	cin >> L >> n;
	if (n == 0) {
		cout << "0 0";
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
	}
	for (int i = 1; i < n; i++) {//从小到大排序
		min = i;
		for (int j = i; j <= n; j++) {
			if (p[j] < p[min])
				min = j;
		}
		MySwap(p[i], p[min]);
	}
	//求最长时间
	maxtime = (L + 1 - p[1]) > p[n] ? (L + 1 - p[1]) : p[n];
	//求最短时间
	for (int i = 1; i <= n; i++) {
		int temp = p[i] < (L - p[i] + 1) ? p[i] : (L - p[i] + 1);
		if (temp > mintime)
			mintime = temp;
	}
	cout << mintime << " " << maxtime;
	return 0;
}

标签:独木桥,int,整数,算法,坐标,士兵,准备,校赛,初始
From: https://www.cnblogs.com/its-my-go/p/18455368

相关文章

  • 代码随想录算法训练营 | 背包问题 二维,背包问题 一维,416. 分割等和子集
    背包问题二维题目链接:背包问题二维文档讲解︰代码随想录(programmercarl.com)视频讲解︰背包问题二维日期:2024-10-09想法:dp[i][j],i表示需要从物品0-i中选择加入到背包中,j表示背包的容量,dp值表示最大的价值;递推公式,如果背包大小j都比此时要放的物品i的weight[i]小了,背包放不下......
  • 代码随想录算法训练营day10| 232.用栈实现队列 225. 用队列实现栈 20. 有效的括
    学习资料:https://programmercarl.com/栈与队列理论基础.html栈与队列学习记录:232.用栈实现队列(两个栈(stack_in,stack_out)实现一个队列的行为)点击查看代码classMyQueue(object):def__init__(self):self.stack_in=[]self.stack_out=[]d......
  • codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报
    解题历程:看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后......
  • 必知的十大计算机视觉算法
    成长路上不孤单......
  • JAVA——常见算法
    查找算法基本查找从0索引开始查找是否找到packagecom.itheima.search;importjava.security.KeyStore;publicclassBasicSearchDemo1{publicstaticvoidmain(String[]args){int[]arr={23,34,54,24,43,46};intnumber=43;......
  • 简明逻辑回归算法
     逻辑回归是一种用于分类问题的统计方法,尽管名称中包含“回归”,但它主要用于二分类任务。为了更好地理解逻辑回归,我们可以通过一个通俗易懂的例子来解释。例子:判断是否通过考试假设你是一名老师,想要根据学生的学习时间来判断他们是否能通过一次考试。我们将“通过考试”定义为......
  • DAY27||回溯算法基础 | 77.组合| 216.组合总和Ⅲ | 17.电话号码的字母组合
    回溯算法基础知识一种效率不高的暴力搜索法。本质是穷举。有些问题能穷举出来就不错了。回溯算法解决的问题有:组合问题:N个数里面按一定规则找出k个数的集合切割问题:一个字符串按一定规则有几种切割方式子集问题:一个N个数的集合里有多少符合条件的子集排列问题:N个数按一定规......
  • 不同的快排算法
    之前写过一篇快排但是现在来看写的很简单,很无聊 快排的思想其实大家都懂这次详细写写不同快排之间的区别和一些优化点 1.首先是pivot元素的选择a.当我们数组本身就是随机的时候,选择第一个/最后一个/中间一个都是可以的,但如果数组是有某种规律的,有可能会退化......
  • 合并、删除区间算法C++代码
    #include<algorithm>#include<iostream>#include<vector>usingnamespacestd;classSolution{public:constintCOMBINE_INT=0;//1表示整数点区间,比如[1:3]和[4:5]会合并为[1:5],0则仅会合并[1:3]和[3:4]这类的区间。vector<pair<int,int>>......
  • 基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数
    1.程序功能描述基于禁忌搜索算法的VRP问题求解matlab仿真,带GUI界面,可设置参数。2.测试软件版本以及运行结果展示MATLAB2022a版本运行 3.核心程序whileCOUNT<=ItertionsֲL=zeros(Ant_Num,1);fori=1:Ant_NumInfor_Tabu_tmps=......