我要招人

去企业版

首页 > 试题广场 >

编程题1

[编程题]编程题1

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

P为给定的二维平面整数点集。定义 P 中某点x，如果x满足 P 中任意点都不在 x 的右上方区域内（横纵坐标都大于x），则称其为“最大的”。求出所有“最大的”点的集合。（所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内）

如下图：实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。

输入描述:

第一行输入点集的个数 N， 接下来 N 行，每行两个数字代表点的 X 轴和 Y 轴。
对于 50%的数据,  1 <= N <= 10000;
对于 100%的数据, 1 <= N <= 500000;

输出描述:

输出“最大的” 点集合， 按照 X 轴从小到大的方式输出，每行两个数字分别代表点的 X 轴和 Y轴。

示例1

输入

输出

4 6
7 5
9 0

算法知识视频讲解

Python

sherrie__

有没有大佬帮忙看一眼呢，写了半天好不容易想明白，但是超时了

n = int(input())
points = []
for i in range(n):
    x, y = map(int, input().strip().split(' '))
    points.append((x,y))
    
points.sort(key=lambda a:-a[1])
x_axis = -1
for x, y in points:
    if x > x_axis:
        print(x, y)
        x_axis = x

发表于 2022-09-11 18:26:06 回复(0)

Python

球球12345

内存不足

N=int(input())
i=0
X=[]
Y=[]
while i<N:
    a,b=input().split(" ")
    X.append(int(a))
    Y.append(int(b))
    i=i+1
datas=zip(X,Y)
datass1=sorted(datas,key=lambda x:x[0])
datass2=zip(*datass1)
X,Y = [list(x) for x in datass2]
for i in range(0,N-1):
    if Y[i]==max(Y[i:N]):
        print(X[i],Y[i],end='\n')
        i=i+1
    else:
        i=i+1   
print(X[N-1],Y[N-1])

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

Python

菜狗爱学习

内存超限:您的程序使用了超过限制的内存

case通过率为80.00%

N= int(input())

l_p = []
for i in range(N):
l_p.append( list(map(int, input().split(' '))) )
l_p.sort(key = lambda x : x[0], reverse=True)
res = []
y_max = l_p[0][1]
for item in l_p :
if item[1] >= y_max :
y_max = item[1]
res.append(item)
#res.sort()
for i in range(len(res)) :
print(res[len(res)-1-i][0], res[len(res)-1-i][1])

发表于 2020-11-22 19:15:50 回复(0)

Python

瑟瑟发抖的菜鸡

通过50% 咋回事
N = int(input())
pos = []

for i in range(N):
line = [int(num) for num in input().split()]
pos.append(line)

pos.sort(key=lambda t: (t[0]))

result = [pos[-1]]

flow = -2
max = pos[-1][1]
while -flow< len(pos):
if pos[flow][1]> max:
result.append(pos[flow])
max= pos[flow][1]
flow-=1
else:
flow-=1

for res in result[::-1]:
print(res[0],res[1])

发表于 2020-05-11 21:33:56 回复(0)

Python

张小草hhhh

python AC 50% 超时了，感觉这道题python没办法不超时。。sort自己写可能会好点，但是python那么多好用的包和函数不就是拿来用的么QAQ，不想改了，50就50，不捞我就独自美丽

n = int(input())
listx=[]
listy=[]
for i in range(n):
    x,y=list(map(int, input().split(" ")))
    listx.append(x)
    listy.append(y)
Z = zip(listx,listy)
Z = sorted(Z)
newx,newy=zip(*Z)
newx=list(newx)
newy=list(newy)
for i in range(n):
    if newy[i]== max(newy[i:]):
        print(newx[i],newy[i])

发表于 2020-05-10 15:47:08 回复(0)

Python

howoo

if __name__ == "__main__":
    n = int(input())
    a = []
    for _ in range(n):
        a.append(list(map(int,input().split())))
    a.sort(key=lambda x: x[0])

    j = len(a) - 2
    tmpy = a[-1][1]

    for i in range(len(a) - 1, -1, -1):
        if tmpy < a[i][1]:
            tmpy = a[i][1]
            a[j] = a[i]
            j -= 1
    for k in range(j + 1, len(a)):
        print(a[k][0], a[k][1])

通过80%，在原来的数组里修改，想不通为啥还是爆内存，怀疑这个python有问题，欢迎大佬指正

编辑于 2019-08-13 20:50:18 回复(2)

Python

🐰201903121141635

cnt =int(input())
every =[]
result =[]
for i in range(cnt):
    num =[int(x) for x in input().split()]
    every.append(num)
every.sort(key=lambda t:t[0])
maxY =-1
for i in reversed(range(len(every))):
    if every[i][1] > maxY:
        result.append(every[i])
        maxY =every[i][1]
for i in reversed(range(len(result))):
    print(result[i][0], result[i][1])

算法和热评第一的大佬一样的……70% 超时或者80%超内存交替出现……有没有大佬救救我

编辑于 2019-04-25 16:18:40 回复(0)