首页 > 其他分享 >洛谷 P1007 独木桥

洛谷 P1007 独木桥

时间:2023-04-20 20:38:54浏览次数:48  
标签:独木桥 洛谷 22 int P1007 士兵 max 初始

题目背景

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

题目描述

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

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

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

输入格式

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

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

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

输出格式

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

输入输出样例

输入 #1
4
2
1 3
输出 #1
2 4

说明/提示

对于 100%100% 的数据,满足初始时,没有两个士兵同在一个坐标,1≤L≤5×103 ,0≤N≤5×103,且数据保证N≤L。

题解

有一座长度为L的桥,桥上有N名士兵,每个士兵朝着某个方向前行直到离开这座桥。但当他们在桥上遇到其他士兵时,需要转过身继续行走。题目中提到“如果两个士兵面对面相遇,他们无法彼此通过对方,于是就分别转身,继续行走。转身不需要任何的时间。”如果给每一个士兵设一个初始方向,当士兵遇到其他人时改变方向,那么会增加代码的复杂度,所以不妨将他们碰面以后的身份互换。

首先求撤离独木桥的最短时间。最短时间其实就是所有人中走完桥最小值中的最大值。首先求出桥一半的长度k,用一个for循环,计算每一个士兵朝某一个方向(向右)下桥的时间t。如果他的初始位置在桥中间的右边(a[i]>k),那么最短时间就是上一个最短和这个士兵下桥时间中较大的一个。如果他的初始位置不在桥中间的右边(a[i]<=k),那么最短时间就是上一个最短时间和这个士兵初始位置中的较大的一个。

然后求最长的时间。如果他的初始位置在桥中间的右边(a[i]>k),那么最长时间就是上一个最长和这个士兵初始位置中的较大的一个。如果他的初始位置不在桥中间的右边(a[i]<=k),那么最长时间就是上一个最长时间和这个士兵下桥时间中较大的一个。

代码

#include <iostream>

using namespace std;

int main()
{
    int l,n,i,x=0,y=0,t=0;
    cin>>l>>n;
    int a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int k=(l+1)/2;
    for(i=0;i<n;i++)
    {
        t=l-a[i]+1;
        if(a[i]>k)
        {
            x=max(x,t);
            y=max(y,a[i]);
        }
        else
        {
            x=max(x,a[i]);
            y=max(y,t);
        }
    }
    cout<<x<<" "<<y;
    return 0;
}

 

标签:独木桥,洛谷,22,int,P1007,士兵,max,初始
From: https://www.cnblogs.com/dachi7/p/17324181.html

相关文章

  • 洛谷 P8456 -「SWTR-8」地地铁铁(图论+结论)
    挺有意思的结论题,结论的证明比较复杂。据出题人说他大概想了几天几夜才证出来,所以本篇题解并不详细给出结论证明,如果有兴趣可以自己去看出题人的题解:https://www.luogu.com.cn/blog/AlexWei/solution-p8456。首先涉及到简单路径,肯定往双连通分量的方向思考。因此我们首先建出圆方......
  • 洛谷P1249最大乘积,数论找规律
    最大乘积题目描述一个正整数一般可以分为几个互不相同的自然数的和,如\(3=1+2\),\(4=1+3\),\(5=1+4=2+3\),\(6=1+5=2+4\)。现在你的任务是将指定的正整数\(n\)分解成若干个互不相同的自然数的和,且使这些自然数的乘积最大。输入格式只一个正整数\(n\),(\(3\leqn\leq10000\))。......
  • 洛谷P5494 【模板】线段树分裂
    传送门  需要的前置知识:线段树合并。  感觉会了线段树合并这个就很简单,线段树分裂就是在把一颗权值线段树值域在[x,y]的区间分裂出来单独成一个线段树,那么我们只需要从新树q和旧树p的根节点一起走,如果走到当前p被[x,y]完全包含的路径就把p的编号给q,并且把p改为0就行了,注意......
  • 洛谷 p1102 A-B数对
    题目背景出题是一件痛苦的事情!相同的题目看多了也会有审美疲劳,于是我舍弃了大家所熟悉的A+BProblem,改用A-B了哈哈!题目描述给出一串正整数数列以及一个正整数 C,要求计算出所有满足A−B=C 的数对的个数(不同位置的数字一样的数对算不同的数对)。输入格式输入共两行。......
  • 洛谷P7492 [传智杯 #3 决赛] 序列 题解 数列分块
    题目链接:https://www.luogu.com.cn/problem/P7492解题思路:分块。解题思路全部来自yzy1大佬的博客额外掌握技能:编译时加入-Wall参数。示例程序:#include<bits/stdc++.h>usingnamespacestd;constintmaxn=1e5+5;intn,m,blo,//n表示数列长度,m表......
  • 洛谷T226686 长度为2的子串
    题目描述给你一个长度为n 的由大写的英文字母组成的字符串,请你找出出现频率最高的长度为2的子串。输入格式包括两行。第一行是一个正整数n,表示字符串长度。第二行是长度为n的大写英文字母组成的字符串。(2<=n<=100)输出格式包括一行。一个长度为2的字符串,该字符串为输入......
  • 【rmq】洛谷P7333
    题目:P7333[JRKSJR1]JFCA-洛谷|计算机科学教育新生态(luogu.com.cn)分析:用rmq处理出各个区间长度的最大值,然后在二分区间长度找到答案(最开始想的是开长度为n的数组,对位置i的数,分别找1-(i-1)和(i+1)-n中的离i最近满足条件的位置,然后更新结果,但一直wa,还没找到问题,存疑吧)代码:......
  • 洛谷 P3292 [SCOI2016]幸运数字
    https://www.luogu.com.cn/problem/P3292多次询问求一条链取若干点的最大异或和考虑一个集合的最大异或和可以求出线性基完成,两个集合的线性基可以合并,但是线性基并没有可减性,于是我们求lca的时候只能每次往集合里添加一条链,为了保证复杂度只能用倍增做。std::vector<i64>......
  • w1 洛谷T233243
      主要思路就是计算每一个长度为2的子串出现的次数,计数的同时用数组记录次数,打擂台找到出现次数最多的子串,首字符出现的位置就是数组的下标。最后输出出现最多的子串。代码如下:#include<bits/stdc++.h>usingnamespacestd;intcnt[100];intmain(){ intn,max=-1; ......
  • 洛谷P2415 集合求和(数学问题,使用集合子集求和公式)
    可以知道对于一个有n个数据的集合,其子集个数有2^n个至于证明可以这样理解,对于n个数据,其子集就是对数据进行组和,而对于每个位置上的数据,组合时仅有两种状态即有此数据或无此数据,也就是有两种可能,而对于n个数据,就有2^n种可能不妨设其中一个非空数据X,对于X,依据X可以将子集划分为两......