我要招人

去企业版

首页 > 试题广场 >

编程题1

[编程题]编程题1

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

牛客281466339号

测试case预期结果是默认的Y值倒序，不是输入的顺序，不符合这个顺序就判定不成功，这个设计是否合理，题目只是找出点的集合，并没有规定顺序。

ps：有没有python通过了，既不超时也没超内存的

编辑于 2021-05-23 17:53:20 回复(2)

Python

譕言

################################

python 3.9 ，内存一直超过限制，正确率80%，看到统计python没有通过的，求大神指导。

################################

import sys

point = {}
point_y = []

num = int(input())
for i in range(num):
input_data = input()
input_data = input_data.split()
point[int(input_data[1])] = int(input_data[0])
point_y.append(int(input_data[1]))

point_y.sort()
point_y.reverse()
x_up_max = point[point_y[0]]
for p in point_y:
if point[p] >= x_up_max:
x_up_max = point[p]
print(point[p],p)

发表于 2021-03-06 05:44:24 回复(0)

Python

Zel201806271023282

倒叙查找，用的python语言，只能通过80%，提示内存超出限制，但是在另外一个同样的题目上，内存限制提高到128M，就能100%通过了

def main():
    n = int(input())
    point_list = []
    max_num = [0,0]
    for _ in range(n):
        data = input().split()
        x, y = int(data[0]), int(data[1])
        if x < max_num[0] and y < max_num[1]:
            continue
        if x > max_num[0] and y > max_num[1]:
            max_num = [x, y]
        point_list.append((x,y))
    point_list.sort()
    result = []
    max_y = 0
    for i in range(len(point_list)-1, -1,-1):
        if point_list[i][1] >= max_y:
            max_y = point_list[i][1]
            result.append(point_list[i])
    for i in range(len(result)-1, -1,-1):
        print(result[i][0], result[i][1])
if __name__ == "__main__":
    main()

编辑于 2020-07-08 22:11:48 回复(0)

Python

Deathstroke-_-

import sys
import math

def takefirst(lis):
    return lis[0]

lines = sys.stdin.readlines()
raw = []
for line in lines:
    raw.append(list(line.strip().split()))
raw = raw[1:]
total = len(raw)
result = []
for raw0 in raw:
    flag = 1
    for raw1 in raw :
        if (raw1 == raw0):
            pass
        elif raw1[0] > raw0[0] and raw1[1] > raw0[1]:
            flag = 0
    if flag == 1:
        result.append(raw0)
result.sort(key=takefirst)
for res in result:
    print(res[0] + ' ' + res[1])

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

case通过率为30.00%

怎么优化啊，菜鸡求指教！

发表于 2020-03-17 19:06:23 回复(0)

Python

探月小畅

Python 70%通过内存超限等一个大神解答~~~

n = int(input())
numdict = {}
for i in range(n):
x,y = map(int,input().split())
numdict[x]=y
numdictsort = sorted(numdict.items(), reverse = True)
numout = {}
numout[numdictsort[0][0]] = numdictsort[0][1]
maxnum = numdictsort[0][1]
for j in range(len(numdictsort)):
if numdictsort[j][1] > maxnum:
numout[numdictsort[j][0]] = numdictsort[j][1]
maxnum = numdictsort[j][1]
for k in sorted(numout.items()):
print('%d %d'%(k[0],k[1]))

发表于 2019-04-12 14:18:16 回复(0)

Python

零碎的杂念

对于任意一个点P，如果存在一个点，x大于它且y大于它，那么它就不能满足条件。也就是说，对于点P，
如果在集合中，找不到另一个点P`，使得P`的x轴，y轴都大于点P，则P点满足条件。 

 class Point(object):
    def __init__(self,x,y):
        self.x = x
        self.y = y
    def isLower(self,point):
        return self.x<point.x and self.y<point.y

num = input()
number = int(num)
li = []
for i in range(number):
    inp = input()
    s = inp.split()
    p = Point(int(s[0]),int(s[1]))
    li.append(p)
res = []
for p1 in li:
    temp = True
    for p2 in li:
        if p1.isLower(p2):
            temp = False
            break
    if temp:
        res.append(p1)
for po in res:
    print ('%d %d'%(po.x,po.y))
（我觉得我的代码没问题。。。）

编辑于 2018-02-07 11:47:33 回复(3)