首页 > 其他分享 >题解 P1007 独木桥

题解 P1007 独木桥

时间:2024-07-14 17:51:28浏览次数:15  
标签:独木桥 题解 最大值 时间 P1007 端出去

link

题意

\(N\) 个人在长度为 \(L\) 独木桥上走动,桥上的坐标为 \(1, 2, \cdots, L\) ,你不知道他们的方向。他们的速度都为 \(1\) 。

  • 当两个人相遇时,他们就分别转身,继续行走。(转身不花费时间)
  • 当某人来到 \(0\) 或 \(L + 1\) 的位置,他就离开了独木桥。

给定 \(N\) 、 \(L\) 和 \(N\) 个人的位置 \(A_i\) ,求所有人离开独木桥花费的最少时间和最多时间。

思路

首先,所有士兵等价,所以两士兵撞上相当于两人**穿过对方然后再走一步 **

但是,可以有多个人同时呆在同一个位置。

eg. 000000101000000 -> 0000100010000

最大值:选择从 \(0\) 端出去,从 \(L + 1\) 端出去的最远距离。

最小值:选择从 \(0\) 端出去,从 \(L + 1\) 端出去的最小距离。

总时间取所有士兵出桥时间的最大值

Code

标签:独木桥,题解,最大值,时间,P1007,端出去
From: https://www.cnblogs.com/lstylus/p/18301819

相关文章

  • 2021杭电多校10 D.Pty hates prime numbers题解
    前言暑期第三次组队赛是选的21年杭电多校10,遗憾爆0,被对面队打爆,赛后狠狠补题。这道题的题解,以及网上搜到的其他题解看了好久没看懂,在问了队里大腿多次后,总算磨出来了,这里讲一下我的理解。题意多次询问,每次给定\(n\)和\(k\),如果一个数的质因数里包括前\(k\)个质数,则这个数......
  • NSIS 之 NsDialogs 常见问题解答
    如何启用/禁用控件使用标准NSIS EnableWindow 命令。NSDialogs允许您弹出通过 ${NSD_Create*} 创建的控件的 hwnd (句柄)。EnableWindow 将 hwnd 作为其参数之一。通过它,您可以轻松启用/禁用控件。  !include"nsDialogs.nsh"!include"winmessages.nsh"!incl......
  • 题解:AT_abc362_d [ABC362D] Shortest Path 3
    一句话题意:给定一个带点权的有权无向连通图,求点1到所有其它点的最短路径。首先,只有1一个起点,所以是单源最短路,又因为最大是\(2\times10^5\),所以是优先队列(堆)优化过后的Dijkstra。所以,我们只需要解决点权的问题就好了。一种显而易见的想法是把与这条边的边权加上起终点......
  • 题解:CodeForces 346A Alice and Bob[博弈/数论]
    CodeForces346AA.AliceandBobtimelimitpertest2secondsmemorylimitpertest256megabytesinputstandardinputoutputstandardoutputItissoboringinthesummerholiday,isn'tit?SoAliceandBobhaveinventedanewgametoplay.Therulesa......
  • 题解:CodeForces 843A Sorting by Subsequences[模拟/排序]
    CodeForces843AA.SortingbySubsequencestimelimitpertest:1secondmemorylimitpertest:256megabytesinputstandardinputoutputstandardoutputYouaregivenasequence\(a_1, a_2, ..., a_n\)consistingofdifferentintegers.Itisrequiredtos......
  • 题解:CodeForces 618C Constellation[贪心/模拟]
    CodeForces618CC.Constellationtimelimitpertest:2secondsmemorylimitpertest:256megabytesinputstandardinputoutputstandardoutputCatNokuhasobtainedamapofthenightsky.Onthismap,hefoundaconstellationwithnstarsnumberedfrom......
  • 题解:CodeForces 835 D Palindromic characteristics[区间dp/马拉车Manacher]
    CodeForces835DD.Palindromiccharacteristicstimelimitpertest:3secondsmemorylimitpertest:256megabytes*inputstandardinputoutputstandardoutputPalindromiccharacteristicsofstring\(s\)withlength\(|s|\)isasequenceof\(|s|\)in......
  • 题解:CodeForces 1019 A Elections[贪心/三分]
    CodeForces1019AA.Electionstimelimitpertest:2secondsmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputAsyouknow,majorityofstudentsandteachersofSummerInformaticsSchoolliveinBerlandforthemostparto......
  • [CF1941E] Rudolf and k Bridges 的题解
    题目大意在第\((i,j)\)个格子修建一个桥墩需要\(a_{i,j}+1\)的花费而且要求\((i,0)\)与\((i,m)\)必须修建桥墩并且桥墩之间的距离不得大于\(d\)。现在需要求见\(k\)个连续的桥,求最小代价。其中\(1\lek\len\le100,3\lem\le2\cdot10,1\led\lem\)。思路因为......
  • [ABC206E] Divide Both 的题解
    题目大意求出从\(l\)至\(r\)中满足以下条件的\((x,y)\)的个数。\(\gcd(x,y)\ne1\)且\(\gcd(x,y)\nex\)且\(\gcd(x,y)\ney\)。其中\(1\lel\ler\le10^6\)。思路正难则反,所以可以求出所有互质或者是相互倍数的\((x,y)\)的对数,在将其减去所有的方案数就是......