首页 > 试题广场 >

谁挡住了我的红绿灯

[编程题]谁挡住了我的红绿灯

热度指数：1048 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

命运的十字路口前，有 $n$ 辆车在等红灯。还来不及思考此刻的选择会将他们带向何方，司机们发现了一个更现实的问题——由于车的高度不尽相同，某些车会因前车的遮挡而无法看到红绿灯。这时候，“谁挡住了谁的红绿灯”便成为一个……很好的笔试题！

现已知红绿灯高度为 $h$ ， $n$ 辆按距离红绿灯由近到远分别标号为 $1 \ldots n$ ，第 $i$ 辆车与红绿灯的距离为 $i$ ，高度为 $a_i$ 。为简化问题，我们以距红绿灯的距离为x轴，高度为y轴建立平面直角坐标系，则红绿灯可抽象为一点 $\left(0,h\right)$ ，第 $i$ 辆车可抽象为线段 $\left(i,0\right)-\left(i,a_i\right)$ 。我们称车 $j$ 挡住了车 $i$ 的红绿灯，当且仅当 $j \lt i$ ，且车 $i$ 看红绿灯的视线，即 $\left(i,a_i\right)$ 与 $\left(0,h\right)$ 的连线与代表车 $j$ 的线段 $\left(j,0\right)-\left(j,a_j\right)$ 相交（含两端）。

现在，我们需要你对每辆车计算谁挡住了它的红绿灯；即对于每一辆车 $i$ ，求最大的 $j$ 满足“车 $j$ 挡住了车 $i$ 的红绿灯”。

输入描述:

第一行包含两个非负整数和；
第二行包含个非负整数。

输出描述:

输出共有行，第行包含对于车的答案，若没有车挡住车，则该行输出0。

示例1

输入

9 5
5 4 3 4 3 3 3 3 3

输出

备注:

20%的数据 $n \leq 10^4$ ；
50%的数据 $n \leq 10^5$ ；
80%的数据 $n \leq 5 \cdot 10^5$ ；
100%的数据 $n \leq 2 \cdot 10^6, 0 \leq h, a_i \leq 10^9$ 。

算法知识视频讲解

风海洋

这么简短的代码，居然超时，它给的测试数据太多了😪😪😪😪

import sys
n,h=map(int,sys.stdin.readline().split())
cars=list(map(int,sys.stdin.readline().split()))
tp=[]
tp.append(0)
for i in range(n):
    for j in range(i-1,-1,-1):
        hight=(h-cars[i])*(i-j)/(i+1)+cars[i]
        if cars[j]>=hight:
            tp.append(j+1)
            break
        if j==0:
            tp.append(0)
for i in range(n):
    print(tp[i])

发表于 2020-09-20 11:53:23 回复(0)

C/C++

freegyp

这题算斜率再用stack做到O(n)，不难理解。关键是这题卡runtime，搞得我不得不用printf和scanf，终于全部通过。

#include<iostream>
#include<cstdio>
using namespace std;
  
int idStack[2000000];
double tangStack[2000000];
  
int main(){
    int n,s=0;double h;cin>>n>>h;
    for(int i=0;i<n;i++){
        double hh;scanf("%lf",&hh);
        double tang = (h-hh)/(double)(i+1);
        while(s>0 && tangStack[s-1]>tang)s--;
        if(s==0)printf("0\n");
        else printf("%d\n",idStack[s-1]);
        idStack[s] = i+1;
        tangStack[s] = tang;
        s++;
    }
    return 0;
}

编辑于 2020-07-15 01:57:26 回复(7)

21CenturyBoy

//算了斜率后用单调栈，讲道理是O（n）啊，只过了70%
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        double h = sc.nextInt();
        double[] height = new double[n];
        for(int i=0;i<n;i++){
            height[i] = sc.nextInt();
        }
        for(int i=0;i<n;i++){
            height[i] = (height[i]-h)/(i+1);
        }
        int[] res = new int[n];
        res[0] = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(0);
        for(int i=1;i<n;i++){
            while (!stack.isEmpty()&&height[i]>height[stack.peek()]){
                stack.pop();
            }
            if(stack.isEmpty())res[i] = 0;
            else res[i] = stack.peek()+1;
            stack.push(i);
        }
        for(int i=0;i<n;i++){
            System.out.println(res[i]);
        }
    }
}

发表于 2020-07-14 19:55:56 回复(5)

Java

pein531

单调栈

思路并不难想，用单调栈来做，可以理解为构建一个“小压大”的单调栈。栈不为空，且当前元素直接压入会破坏单调性时（栈顶车辆不会挡住当前车辆的视线）进行弹栈。

那么如何判断车辆 $j$ 会遮挡车辆 $i$ 的视线呢？需要一些数学方法。

根据上图，我们可以计算得到 $h$ 到 $a_i$ 的连线方程 $y=-\frac{h-a_i}{i}*x+h$ ，然后我们把 $j$ 代入方程，如果得到的值没有超过 $a_j$ ，即 $-\frac{h-a_i}{i}*j+h \leq{a_j}$ ，就说明车辆 $j$ 会遮挡车辆 $i$ 的视线。注意在计算时把除法判断转换为等效的乘法判断，防止浮点数不精确可能会产生影响，并将整型转长整型防止溢出。

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]);
        int h = Integer.parseInt(params[1]);
        params = br.readLine().split(" ");
        int[] heights = new int[n + 1];
        heights[0] = h;
        for(int i = 0; i < n; i++){
            heights[i + 1] = Integer.parseInt(params[i]);
        }
        int[] res = new int[n + 1];
        Stack stack = new Stack();
        for(int i = 1; i <= n; i++){
            while(!stack.isEmpty() && check(stack, heights, i, h)){
                int top = stack.pop();
                res[top] = stack.isEmpty()? 0: stack.peek();
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            res[stack.pop()] = stack.isEmpty()? 0: stack.peek();
        }
        for(int i = 1; i <= n; i++){
            System.out.println(res[i]);
        }
    }

    private static boolean check(Stack stack, int[] heights, int i, int h) {
        int j = stack.peek();
        return (long)i * heights[j] < (heights[i] - h) * (long)j + (long)h*i;
    }
}

讲道理已经是O(N)的时间复杂度了，但一直过不了。这个题卡时间卡得有点无语，改成C++还会卡打印API的时间，离离原上谱，知道思路就好了吧。

编辑于 2022-04-20 17:51:01 回复(0)

跨专业转码好难

#include <iostream>
#include <stack>
#include <vector>

using namespace std;
  
int main()
{
    int n;
    double h;
    cin >> n >> h;
    vector<double> slope (n, 0.0);
    for (int i = 0; i < n; i++)
    {
        cin >> slope[i];
        slope[i] = (slope[i] - h) / (i + 1);
    }
    stack<int> s;
    for (int i = 0; i < n; i++)
    {
        while (!s.empty() && slope[s.top()] < slope[i])
            s.pop();
        if (s.empty())
            printf("0\n");
        else
            printf("%d\n", s.top() + 1);
        s.push(i); 
    } 
}

发表于 2023-07-16 09:22:24 回复(0)

Python

李peak

import sys
n,h=map(int,sys.stdin.readline().split())
cars=list(map(int,sys.stdin.readline().split()))
tan=[]
for i in range(n):
    tmp=(h-cars[i])/float(i+1)
    x=i-1
    if len(tan)==0&nbs***bsp;m***t;tmp:
        print(0)
    else:
        while(len(tan)>0 and x>=0):
            if tan[x]>tmp:
                x-=1
            else:
                break
        print(x+1)
    tan.append(tmp)

我觉得python这么写应该不能再快了吧，但是还是超时了。

由于红绿灯的高度固定，所以算法本身就是找之前的tan是不是不比现在的大，大就是不在线上，小于等于就会阻挡车的视野

编辑于 2021-04-04 20:27:39 回复(0)

yuzu_9497

#只有25.5分，不知为什么运行时间很长
n,h=map(int,input().split())
car_old=list(map(int,input().split()))
car=[0]*(n+1)
car[1:]=car_old
car_old.clear()
res=[0]*(n+1)
kk=[0]*(n+1)
for i in range(1,n+1):
    kk[i]=(car[i]-h)/i 

print(res[1])
for i in range(2,n+1):
    bef=i-1
    while bef>0:
        if kk[i]<=kk[bef]:
            res[i]=bef
            break
        elif res[bef]==0:
            break
        bef=res[bef]
    print(res[i])

编辑于 2021-03-24 10:17:41 回复(0)

牛客497864927号

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

int ans[1000001], stack[1000001];
double ratio[1000001];

int main()
{
	int n, h;
	scanf("%d%d", &n, &h);
	for (int i = 1; i <= n; ++i)
	{
		int a;
		scanf("%d", &a);
		ratio[i] = (a-h)/(double)i;
	}
	
	int top = 0;
	stack[top] = 1;
	for (int i = 2; i <= n; ++i)
	{
		while (top != -1 && ratio[stack[top]] < ratio[i])
			top--;
		if (top >= 0)
			ans[i] = stack[top];
		stack[++top] = i;
	}
	
	for (int i = 1; i <= n; ++i)
		printf("%d\n", ans[i]);

	return 0;
}

发表于 2020-09-22 13:36:31 回复(0)

始于初见^O^桃

//时间复杂度太高，通过20%
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int h = scanner.nextInt();
        int[] car = new int[n];
        for(int i= 0 ; i < n ; i++){
            car[i] = scanner.nextInt();
        }
        System.out.println(0);
        for( int i  = 1 ; i < n ; i++){
            double a = car[i] - h;
            double b = i + 1;
            double k = a / b;
            int m = 0;
            for (int j = i - 1; j >= 0; j--) {
                double y = k * (j + 1) + h;
                if (y <= car[j]) {
                    System.out.println(j + 1);
                    break;
                }else {
                    m = m + 1;
                }
                if(m == i)
                    System.out.println(0);
            }
        }
    }
}

发表于 2020-09-10 17:07:51 回复(0)

Rewindding

#include <bits/stdc++.h>
using namespace  std;
int N,H;
double arr[(int)1e8+10];
int last[(int)1e8+10];
void solve(){
    if(N<=1) return;
    last[0]=-1;
    for(int i=0;i<N;++i){
        int p=i-1;
        while(p>=0&&arr[p]>arr[i]) p=last[p];
        last[i]=p;
        cout<<(p+1)<<'\n';
    }
}
int main(){
    cin>>N>>H;
    int t;
    for(int i=0;i<N;++i){
        cin>>t;
        //height[i]=t;
        arr[i]=(H-t)/(double)(i+1);
    }
    solve();
    return 0;
}

求出每个夹角的tan，然后它左边第一个tan比他小的就是会挡住它的，

发表于 2020-09-02 11:37:41 回复(0)

牛客670418642号

N, H = [int(val) for val in input().split()]
arr = [int(val) for val in input().split()]

def func(N, H, arr):
    stack = []
    res = [0] * (1 + N)
    for i in range(N):
        arr[i] = (arr[i] - H) / (i+1)
        cur = None
        while stack != [] and arr[i] > arr[stack[-1]]:
            cur = stack.pop()
        res[i+1] = 0 if stack == [] else stack[-1]+1 
        stack.append(i)
        print(res[i+1])

func(N, H, arr)

发表于 2020-08-21 13:23:42 回复(1)