There is a small, one-way bridge that can carry a maximum weight of U units at a time. There is also a line of N cars waiting to cross the bridge. The weights of the cars are given as an array weight. The weight of the K-th car in the line is weight[K] (for K within the range [0..N-1]). The car that will enter the bridge first weighs weight[0], the car that will enter second weighs weight[1], and so on. At most two cars can be on the bridge at the same time. To begin, the first two cars in line will enter the bridge. Then the third car will enter the bridge as soon as the first car leaves the bridge, the fourth car will enter when the second car leaves, and so on. The cars leave the bridge in the same order they entered it. However, this may lead to a situation where cars exceed the bridge's weight limit. To prevent such a situation, some drivers have to turn back. When a driver turns back, all drivers behind them in line move one position closer to the bridge. The driver who turns back is removed from the line and will not try to cross the bridge again. Your task is to find the minimum number of drivers that must turn back so that the bridge will not be overloaded. Function Description Write a function: class Solution { public int solution(int U, int[] weight); } that, given an integer U representing the weight limit of the bridge and an array weight of N integers representing the weights of the cars in line, returns the minimum number of drivers that must turn back so that the bridge will not be overloaded.

解法

两车配对：第 i 辆与第 i+1 辆同时上桥(i 与 i 偏移 1 配对)。模拟队列：维护"在桥上"的两个槽位(前车和后车)，按顺序扫描 weight，每次新车进入时：若 front+new > U，新车必须 turn back(front 仍占着，等 front 离开后 new 的"位置"由下一辆候选填补)；否则 front 离开，new 上桥。本质：贪心配对 i 和 i+1，若总和 > U 就把"after"那辆移除。维护两个指针 front(前一辆当前在桥)和遍历 i。时间 O(n)。

from typing import List

def min_turn_back(U: int, weight: List[int]) -> int:
    # Simulate: at any moment there are at most 2 cars on bridge.
    # The "older" car on the bridge stays until the next-in-line either pairs with it (<=U) or that next-in-line turns back.
    removed = 0
    front = None  # weight of the older car currently on the bridge
    for w in weight:
        if front is None:
            front = w
        else:
            if front + w <= U:
                # w boards; front leaves (FIFO). Now w becomes the new front.
                front = w
            else:
                # w must turn back. front stays.
                removed += 1
    return removed

class Solution {
    public int solution(int U, int[] weight) {
        int removed = 0;
        Integer front = null;
        for (int w : weight) {
            if (front == null) {
                front = w;
            } else if (front + w <= U) {
                front = w;
            } else {
                removed++;
            }
        }
        return removed;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solution(int U, vector<int>& weight) {
        int removed = 0;
        int front = -1;
        for (int w : weight) {
            if (front < 0) front = w;
            else if (front + w <= U) front = w;
            else removed++;
        }
        return removed;
    }
};