单车道桥梁问题

Question

如果您不熟悉这个问题，它类似于 这个。

我不是来寻求答案的，我其实已经写完了所有的代码。我刚刚发现我的解决方案并不能以最佳方式解决这个问题，因为我的解决方案一次只允许一辆车在桥上行驶。我希望我能得到一些关于如何使用 sem_wait 和 sem_post 来解决这个问题的提示。我希望让同一个方向的流量能够汇聚在一起，而不是一次一个。

我的解决方案目前看起来像这样：（

默认 sem_t 北和南 = 1 表示 1 辆车解锁）

如果 Northcar 则 sem_wait(south)、sem_wait(north)。过桥，然后是sem_post（北），sem_post（南）。这显然是错误的，因为它锁定了桥上除了桥上那辆车之外的所有车辆。我想让交通能够流动在一起。有什么想法吗？

我使用随机生成的流量，这增加了一些复杂性。

Answer 1

在现实生活中，您可以使用北红/南绿、北绿/南红或北红/南红的交通灯来解决这个问题，并在入口车道和出口车道上安装传感器桥的两端。

假设光线开始时为北红/南绿。汽车可以从南向北不停地行驶。当汽车从北方驶来时，它会在红灯处停下来并触发北方接近传感器。这使得光线向南偏红，但仍然向北偏红。当桥上当前的所有车辆都离开时（在离开时触发北出口传感器），指示灯会变为绿色北向。该状态一直持续到另一辆车从南方驶来并触发南方接近传感器。

考虑一下如何将其转换为代码。 （您需要使用信号量的计数属性。）

Answer 2

单车道高速公路
问题描述
一定数量的汽车正在通过单车道道路。所有汽车的速度各不相同。很容易看出，根据汽车的速度，将形成不同的组。

单车道道路不允许超车。给定汽车的速度，计算如果考虑所有可能的排列，可以形成多少个组。请参阅示例 1 以更好地理解。

打印组数除以排列数。

约束

0 <= N < 10 ^ 5

0 <= speed of individual vehicle < 10 ^ 9

输入
第一行包含一个整数 N，表示车辆的数量。

第二行包含 N 个空格分隔的整数，表示单个车辆的速度。

输出
打印组数除以排列数，四舍五入到小数点后 6 位。

时限
1

示例 1

输入
3

10 20 30

输出

1.833333

解释：

因此所有可能的排列为：

{10 20 30}
{10 30 20}

{20} {10 30}
{20 30} {10}
{30} {10 20}
{30 20} {10}

因此，这里共有 6 种排列，总组数为 11。

因此，输出为 11/6 = 1.833333

示例 2

输入
4

56 78 13 92

输出

2.083333

解释：

所以这里一共有24种排列，

例如：

{56 78 13 92}
{92} {13 78 56}
{56} {13 92 78}
{78 92} {13 56}
.
.

等等。组总数为 50。

因此，输出为 50/24 = 2.083333

Answer 3

这是我刚刚创建的一些伪 python。基本上封锁一条路并让有限数量的汽车通过。根据您使用变量的方式，这可能是完全错误的：

function main():
    while(true):
        if(north_car):
            let_north_cars_through()
        if(south_car):
            let_south_cars_through()


function let_south_cars_through():
    sem_wait(north)
    for(i = 0; i < max cars; i++):
        if(south_car):
            cross_bridge()
        else:
            break;

    sem_post(north)

function let_north_cars_through()
    sem_wait(south)
    for(i = 0; i < max cars; i++):
        if(north_car):
            cross_bridge()
        else:
            break;

    sem_post(south)