我要招人

去企业版

首页 > 试题广场 >

编程题1

[编程题]编程题1

热度指数：21245 时间限制：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

牛客509142031号

import sys
pos = []
for line in sys.stdin:
    a = line.split()
    if len(a) == 1:
        N = int(a[0])
    else:
        pos.append((int(a[1]),int(a[0])))
pos.sort(reverse=True)
pre_x = 0
for i in range(len(pos)):
    if pos[i][1] > pre_x:
        print(pos[i][1], pos[i][0])
        pre_x = pos[i][1]

运行超时通过案例7/10, 有没有老哥python 过了的

发表于 2023-03-01 21:05:30 回复(0)

Python

暮雪丶

运行时间超限制，还需要减少一次打印的循环？

import sys
arr=[ [int(i.split()[0]),int(i.split()[1])] for i in sys.stdin if len(i.split())==2]
arr.sort(key=lambda x:x[0])
max = arr[-1][1]
for i in range(len(arr)-1,-1,-1):
    p=arr[i]
    if max <= p[1]:
        max = p[1]
    else:
        arr.pop(i)
for i in range(len(arr)):
    print(arr[i][0],arr[i][1])

编辑于 2022-09-27 19:21:51 回复(0)

Python

小neo啊啊啊

点解超内存了？

import sys

def zuida(N, sorted_points):
    result = []
    maxY_so_far = 0
    for point in sorted_points:
        if point[1] >= maxY_so_far:
            maxY_so_far = point[1]
            result.append(point)
    result.reverse()
    return result

if __name__ == "__main__":
    line = sys.stdin.readline().strip()
    data = list(map(int, line.split()))
    N = data[0]
    points = []
    for i in range(0, N):
        line = sys.stdin.readline().strip()
        points.append(list(map(int, line.split())))
    sorted_points = sorted(points, key=lambda k: [k[0], k[1]])
    
    sorted_points.reverse()
    

    for r in zuida(N, sorted_points):
        print r[0], 
        print r[1]

发表于 2021-10-24 08:22:54 回复(0)

Python

牛客481733148号

N = int(input())
point_set = []
for _ in range(N):
    x, y = [int(x) for x in input().split()]
    point_set.append((x, y))
point_set.sort(key=lambda x: x[1])
point_set.reverse()

max_x = float('-inf')
for x, y in point_set:
    if x > max_x:
        print(x, y)
        max_x = x

90% 超内存了

发表于 2020-10-23 20:47:18 回复(0)

Python

ToveHou

不知为何我的代码输出顺序有问题..
n = int(input())
A = {}
for item in range(n):
    x,y = map(int,input().split())
    A[x] = y
    pass
B = sorted(A.items(),key=lambda d : d[0] , reverse=True)
#沿x方向排序得到B
#将不满足条件的项从字典A中删除
a = B[0][1]
del B[0] # 最右侧的点一定输出
for item in B:
    if item[1]>a:
        a = item[1]
    else:
        del A[item[0]]
for key,value in A.items():
    print('{} {}'.format(key , value))

编辑于 2020-08-09 00:18:13 回复(0)

Python

ArcherV

p = []
n = int(input())
for i in range(n):
    tmp = input()
    a = [int(x) for x in tmp.split(' ')]
    p.append(a)
sorted(p, key=lambda x: (-x[0], -x[1]))
tmp = -1
for t in p:
    if t[1] > tmp:
        print('%d %d' % (t[0], t[1]))
        tmp = t[1]

发表于 2019-08-06 10:35:39 回复(1)

Python

a1ca4b

p=[]
n=int(input())
for i in range(n):
    a=list(map(int,input().split(' ')))
    p.append(a)

p = sorted(p)
p1 = sorted(p,key=lambda x:x[1])

k = -1
for i in range(n):
    if p[i]==p1[-1]:
        temp = str(p[i][0]) + ' ' + str(p[i][1])
        print(temp)
        p1.pop()
        k = p[i][0]
    while p1 and p1[-1][0] < k:
        p1.pop()

#case：70%，尽全力啦，望指教

编辑于 2019-03-23 19:19:02 回复(0)

Python

麻瓜工程师

import sys
n = int(sys.stdin.readline())
x = [0]*n
y =[0]*n
for i in range(n):
    temp = list(map(int,sys.stdin.readline().split()))
    x[i] = temp[0]
    y[i] = temp[1]
new = sorted(list(zip(x,y)),key = lambda x:x[0])
for x,y in new:
    for x1,y1 in new:
        if x1 > x and y1 > y:
            break
    else:
        print(x,y)

运行时间超限制

发表于 2018-03-27 04:34:25 回复(0)

Python

十月顺利！

n=int(raw_input())
ps=[]
for _ in range(n):     x,y = raw_input().split(' ')     ps.append((int(x),int(y)))
ps.sort(reverse=True)
y_max=ps[0][1]
maxx=[]
for i in ps:     y_i = i[1]     if y_i>=y_max:         y_max=y_i         maxx.append(i)
maxx.sort()
for i in maxx:     print '%s %s'%(i[0], i[1])