首页 > 试题广场 > 谁挡住了我的红绿灯
[编程题]谁挡住了我的红绿灯
  • 热度指数:809 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

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


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

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

输入描述:
第一行包含两个非负整数
第二行包含个非负整数


输出描述:
输出共有行,第行包含对于车的答案,若没有车挡住车,则该行输出0。
示例1

输入

9 5
5 4 3 4 3 3 3 3 3

输出

0
1
2
1
4
4
4
4
1

备注:

20%的数据 
50%的数据 
80%的数据 
100%的数据 

这题算斜率再用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)
//算了斜率后用单调栈,讲道理是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)
这么简短的代码,居然超时,它给的测试数据太多了😪😪😪😪
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)
#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)
//时间复杂度太高,通过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)
#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)
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)

热门推荐

通过挑战的用户