P为给定的二维平面整数点集。定义 P 中某点x,如果x满足 P 中任意点都不在 x 的右上方区域内(横纵坐标都大于x),则称其为“最大的”。求出所有“最大的”点的集合。(所有点的横坐标和纵坐标都不重复, 坐标轴范围在[0, 1e9) 内)
如下图:实心点为满足条件的点的集合。请实现代码找到集合 P 中的所有 ”最大“ 点的集合并输出。
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轴。
5 1 2 5 3 4 6 7 5 9 0
4 6 7 5 9 0
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 过了的
运行时间超限制,还需要减少一次打印的循环?
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])
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]
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
不知为何我的代码输出顺序有问题..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))
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%,尽全力啦,望指教
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)运行时间超限制
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])
80%,内存超限