首页 > 试题广场 >

编程题1

[编程题]编程题1

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

算法知识视频讲解

phlirock


	#include<bits/stdc++.h>



	#define frp(i,a,b) for(int i = a; i <= b; i++)



	#define frpp(i,a,b) for(int i = a; i < b; i++)



	#define frd(i,a,b) for(int i = a; i >= b; i--)



	#define frdd(i,a,b) for(int i = a; i > b; i--)



	#define clr(a,b) memset(a,b,sizeof(a))



	#define pb push_back



	#define mp make_pair



	#define lb lower_bound



	#define ub upper_bound



	 



	usingnamespacestd;



	typedeflonglonglint;



	 



	structnod{



	    intx,y;



	    booloperator < (constnod & a)const{



	        returnx < a.x;



	    }



	}a[500050];



	intn;



	 



	inlinevoidget_ready( )



	{



	    scanf("%d", &n);



	    frp(i,1,n)  scanf("%d%d",&a[i].x,&a[i].y);



	}



	 



	inlinevoidsolve( )



	{



	    sort(a+1,a+n+1);



	    stack<nod>qq;



	    intres;



	    frd(i,n,1){



	        if(qq.empty()){



	            qq.push(a[i]);



	            res = a[i].y;



	        }



	        else{



	            if(a[i].y>res){



	                qq.push(a[i]);



	                res = max(res,a[i].y);



	            }



	        }



	    }



	    while(!qq.empty()){



	        nod xx = qq.top( );



	        qq.pop( );



	        printf("%d %d\n",xx.x,xx.y);



	    }



	}



	 



	intmain( )



	{



	    get_ready( );



	    solve( );



	    return0;


}

编辑于 2017-12-27 08:48:03 回复(0)

PPHT

python有不超内存的方法吗？我连备用数组都去掉了，还是不行。。。

n = int(input())
points = [[int(j) for j in input().split()] for _ in range(n)]

points.sort(key=lambda x: x[0])

index=-2
y = points[-1][1]
for _ in range(n-1):
    if y >= points[index][1]:
        del points[index]
    else:
        y = points[index][1]
        index-=1

for i in range(len(points)):
    print('%d %d' % (points[i][0],points[i][1]))

发表于 2020-09-24 14:31:41 回复(0)

C/C++

黄小贤工匠

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<stdio.h>
#include<algorithm>
#include<limits.h>
 
using namespace std;
 
struct Point {
 
    int x;
    int y;
 
    Point(int a, int b) :x(a), y(b) {
     
    }
 
    bool operator>(Point& other) {
     
        return x > other.x;
    }
};
 
bool cmp(Point x1, Point x2) {
 
    return x1.x > x2.x;
}
 
vector<Point> maxPoint(vector<Point>& nums) {
 
    int size = nums.size();
    vector<Point> ret;
    sort(nums.begin(), nums.end(), cmp);
    ret.push_back(nums[0]);
    int tempY = nums[0].y;
    for (int i = 1; i < size; i++) {
 
        if (nums[i].y > tempY) {
 
            ret.push_back(nums[i]);
            tempY = nums[i].y;
        }
    }
 
    return ret;
}
 
int main()
{
    int n;
    cin >> n;
    vector<Point> nums(n, Point(0, 0));
    vector<Point> ret;
 
    for (int i = 0; i < n; i++) {
            // 注： 这里使用cin 输入会导致超时，只能通过80%例子 
        //cin >> nums[i].x >> nums[i].y;
        scanf("%d %d\n", &nums[i].x, &nums[i].y);
    }
 
    ret = maxPoint(nums);
 
    for (int i = ret.size() - 1; i >= 0; i--) {
 
        cout << ret[i].x << " " << ret[i].y << endl;
    }
     
    return 0;
}

发表于 2018-08-16 15:30:22 回复(1)

Noah4

if __name__ == "__main__":
    n = int(input())
    point = []
    for i in range(n):
        line = input()
        x, y = list(map(int, line.split()))
        point.append((x, y))
    point.sort()
 
    last_height=point[-1][1]
    for i in range(n-2,-1,-1):
        if point[i][1]>last_height:
            last_height=point[i][1]
        else:
            del point[i]
 
    for i in point:
        print("%d %d"%(i[0],i[1]))

80% 超时

一开始是内存超限，改用del方式就变成超时了。。。

发表于 2020-08-19 11:28:48 回复(0)

Castile

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.util.Stack;

class point implements Comparable<point>{
    long x;
    long y;

    public point(long x, long y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return this.x +" "+this.y;
    }

    @Override
    public int compareTo(point o) {
        // TODO Auto-generated method stub
        return (int) (o.x - this.x);
    }



}
public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int num = sc.nextInt();

        ArrayList<point> P = new ArrayList<point>();


        // 输入数据
        for(int i = 0; i < num; i++){
            long x = sc.nextLong();
            long y = sc.nextLong();
            point p = new point(x, y);
            P.add(p);
        }
//        P.sort(new Comparator<point>() {
//
//            @Override
//            public int compare(point o1, point o2) {
//                // TODO Auto-generated method stub
//                return (int) (o2.x - o1.x);
//            }
//        });
        Collections.sort(P);

        Stack<point> s = new Stack<point>();

        long maxy = -1;
        for(int i = 0; i < num; i++)
        {
            //System.out.println(P.get(i));
            point p = P.get(i);
            long y = p.y;
            if(y >= maxy){
                maxy = y;
                s.push(p);
            }

        }

        while(!s.isEmpty()){
            point p = s.pop();
            System.out.println(p.x+" "+p.y);
        }




    }

}

编辑于 2019-03-14 10:31:04 回复(0)

何恺明的小迷妹

只是输出的顺序和答案不一样，竟然不让过。。。

发表于 2018-03-19 21:21:26 回复(3)

chestnut7

PYTHON

import sys 
n = int(sys.stdin.readline().strip())
point = []
for i in range(n):
    point.append(list(map(int, sys.stdin.readline().strip().split())))
point.sort(key=lambda k:k[1],reverse=True)

res = []
res.append(point[0])
for i in  range(1,len(point)):
    if point[i][0] > res[-1][0]:
        res.append(point[i])
    else:
        continue 
res.sort(key=lambda k:k[0])
for i in res:
    print i[0],i[1]

您的代码已保存
内存超限:您的程序使用了超过限制的内存
case通过率为80.00%

发表于 2018-08-10 16:34:58 回复(5)

Sju


	
/*
思路解析：
题目要求我们需要输出的是，存在满足没有(x,y)同时大于他的点。
因此，通过分析可以知道，如果先将x按降序排序。那么我们每次只需要更新最大的y就好了。
因为，之后的出现的x不可能会比之前的大，那么满足输出的情况只要一种了，
就是之后的某个点的y比之前的大。
*/
#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <stack>



using namespace std;



const int MAXN = 500000 + 10;



struct Point{

    int x, y;

    Point(){};

    Point(int _x, int _y):

        x(_x), y(_y) {};

    bool operator < (const Point &rhs) const {

        return x > rhs.x;

    }



} p[MAXN];







/*

 *

 *

5

1 2

5 3

4 6

7 5

9 0



*/

int main(int argc, char* argv[])

{



    int n;

    while(~scanf("%d",&n)) {

        int x, y;

        for (int i = 0;i < n;++i) {

            scanf("%d%d", &x, &y);

            p[i].x = x;

            p[i].y = y;

        }



        sort(p, p+n);

//        for (int i = 0;i < n;++i) {

//            cout << p[i].x <<" " << p[i].y << endl;

//        }

        stack<Point> s;

        int maxy = -1;



        for (int i = 0;i < n;++i) {

            if (maxy <= p[i].y) {

                maxy = p[i].y;

                s.push(Point(p[i].x, p[i].y));

            }

        }



        Point tmp;

        while(!s.empty()) {

            tmp = s.top();

            s.pop();

            printf("%d %d\n", tmp.x, tmp.y);

        }



    }

    return 0;

}

编辑于 2018-03-19 16:35:26 回复(6)

Reyzal

本套试题AC代码在 https://github.com/ReyzalX/nowcoder 查看

#include <bits/stdc++.h>

using namespace std;

struct Point
{
    int x, y;
};

Point points[500001];

int main()
{
    int n;
    cin >> n;
    for (size_t i = 0; i < n; i++)
    {
        scanf("%d%d", &points[i].x, &points[i].y);
    }
    //按照y升序 x降序排列
    sort(points, points + n,
         [](Point & p1, Point & p2)
    {
        return p1.y == p2.y ? p1.x > p2.x : p1.y < p2.y;
    });
    printf("%d %d\n", points[n - 1].x, points[n - 1].y);
    int maxx = points[n - 1].x;
    for (int i = n - 2; i >= 0; i--)
    {
        if (points[i].x > maxx)
        {
            printf("%d %d\n", points[i].x, points[i].y);
            maxx = points[i].x;
        }
    }
    return 0;
}

发表于 2018-03-12 17:16:15 回复(5)

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

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)

噗通一声跳下水

from sys import stdin
n =int(stdin.readline().strip())
data= [int(x) for x in stdin.readline().strip().split()]
partsum=[0]
for x in data:
    partsum.append( partsum[-1]+x )

def left_bound(data):
    left=[ 0 for i in range(n) ]
    for i,v in enumerate( data[1:],1):
        if v > data[i-1]:
            left[i]=i
        else:
            k = i-1
            while k >= 0:
                if v < data[k]:
                    k = left[k]-1
                else :
                    left[i] = left[k] if v == data[k] else k+1
                    break
    return left

left = left_bound(data)
right= left_bound(data[::-1])[::-1]
right= [n-x for x in right ]

res = max([ data[i]*(partsum[right[i]]-partsum[left[i]]) for i in range(n) ])
print(res)

思路是：把每个数当做区间里的最小值，找区间左右边界，即第一个小于它的数（区间里加入小于它的数，它就不是最小值了）

优化的点有两个：

1.求和涉及大量的重复运算——可以用从0到n的部分和减法代替

2.找边界的过程涉及大量的重复比较——

以找左边界为例，从第二个数起，

如果大于前一个数，则左边界为自身；否则：

如果等于前一个数，则左边界跟前一个数的左边界一样；

如果小于，则它的左边界小于前一个数的左边界；

这样可以跳过重复的比较。

把找左边界写成函数，求右边界把数组逆置调用下再转换就行了，不用重写

完美AC

编辑于 2019-08-14 11:10:42 回复(0)

饮茶神仙

首先要找到y值最大的点,设其为(x0,y0)

对于点(x1,y1)当x1<x0&&y1<y0时明显不符合，（实际上只用比较x1<x0）所以在y左侧的所有点都被排除范围内，删除所有x<x0的点

所以我们的方法是建立两个数组，分别按x值，y值排序

循环为：

1)提取出y值最大的点x0,y0，找到这个点在另一数组的位置

2)移除所有x排序中在该点以前的坐标，将该点装入最大点集合

中止条件为初试数组内不存在其他值

复杂度为O(nlogn)

实际上用map存可以省去排序的过程，复杂度应该能到O(logn)，这里不赘述

编辑于 2020-04-09 16:46:22 回复(0)

伤逝201808131744503

import numpy as np 
p=[]

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

p=np.array(p)
indx=np.argmax(p,axis=0)
#TODO 构造直线方程
x1=p[indx[0]][0]
y1=p[indx[0]][1]
x2=p[indx[1]][0]
y2=p[indx[1]][1]
a = y2-y1
b = x1-x2
c = x2*y1-x1*y2
for j in range(n):
    x=p[j][0]
    y=p[j][1]
    distance=a*x+b*y+c
    if distance>=0:
        print(p[j][0]+p[j][1])

x轴最大值和y轴的最大值对应的坐标构造一条直线方程，将所有点代入到直线方程，大于0就满足。

发表于 2019-03-15 11:21:47 回复(4)

走四方ya

这道题目有通过java ac的吗？我思路一样，但是提交只能通过70%

发表于 2018-08-29 13:41:43 回复(3)

linlinlin14250

1.本题能正确通过的思路是：按照一个轴（x或者y）升序排序，然后从最后一个元素开始，始终与（y后者x）最大元素做对比，如果比最大元素大，就保存到栈中或者vector中，然后把最大元素更新；如果小于最大元素，那么就查看下一个元素。

2.本题有些小的细节，如果不能够注意那么就无法通过编译。首先，是要用printf打印而不要用cout打印，然后是a.y==b.y?a.x>b.x:a.y<b.y;（按照y轴升序，按照x轴降序），这样做要比单纯地按照a.y<b.y

（按y轴升序）快，不知道是为什么（因为题目中说x轴和y轴的元素都是不相等的），希望有大神指点一下。

发表于 2018-03-26 11:43:14 回复(2)

牛客6603804号

#include<iostream>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
static bool cmp(const vector<int>& a,const vector<int>& b){
    return a.front()>b.front();
}
//该题减少时间复杂度的关键在于，按照x降序排列，那么只要记录前面这些点的最大y值maxy，
//只要该点的y值比这个maxy大，那么就不存在x和y同时大于它的情况，而不需要一一比较
int main(){
    int num;
    cin>>num;
    vector<vector<int>> nums(num,vector<int>(2));
    for(int i=0;i<num;i++){
        cin>>nums[i][0]>>nums[i][1];
    }
    sort(nums.begin(),nums.end(),cmp);
    int maxy=-1;  
    stack<int> s;
    for(int i=0;i<nums.size();i++){
            if(nums[i][1]>maxy){
                maxy=nums[i][1];
                s.push(i);
            } 
    }
    while(!s.empty()){
    cout<<nums[s.top()][0]<<" "<<nums[s.top()][1]<<endl;
    s.pop();
    }

        return 0;
    
}

发表于 2022-07-08 10:41:04 回复(0)

幻世一梦


	#include <iostream>



	#include <algorithm>



	#include <vector>



	using namespace std;



	 



	int n;



	typedef struct point {



	    long long x, y;



	} Point;



	vector<int> v;



	 



	bool compPoint(Point p1, Point p2) {



	    if(p1.x > p2.x) return true;



	    if(p1.x == p2.x && p1.y > p2.y) return true;



	    return false;



	}



	int main() {



	    cin >> n;



	    Point *p = new Point[n];



	    for(int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;



	    sort(p, p + n, compPoint);



	    long long max_y = -1;



	    for(int i = 0; i < n; i++) {



	        if(p[i].y >= max_y) {



	            v.push_back(i);



	            max_y = p[i].y;



	        }



	    }



	    int L = v.size();



	    for(int i = L - 1; i >= 0; i--) printf("%ld %ld\n", p[v[i]].x, p[v[i]].y);



	    return 0;



	}

排序（x降序，x相同y降序），从后向前遍历，更新当前最大的y值

注意最后用printf输出，cout会超时，只能过80%

发表于 2019-04-17 17:54:56 回复(0)

IFAN0823

# import numpy as np
n = int(input())
arr = []
for i in range(n):
    line = input().split(' ')
    line =[int(n) for n in line]
    arr.append(line)
# sorted_arr = arr[np.argsort(arr[:, 0])]
arr = sorted(arr,key = lambda x:x[0])
y_max = -1
i = len(arr)-1
res=[]
while(i>0):
    # print(arr[i])
    if(arr[i][1]>y_max):
        y_max = arr[i][1]
        res.append(arr[i])
    i-=1
i = len(res)-1
while(i>=0):
    print(f"{res[i][0] } {res[i][1]}")
    i-=1

我这样理解，针对二维数组的第一维进行排序，然后利用res存放输出的点，
从后往前遍历二维数组arr，以次记录y的最大值。
因为x轴本来就是升序的，故当前的x坐标肯定大于下一个点的x坐标，
只需要比较当前轴的y值和记录的y最大值，只要y的最大值更新，就存放在res中，
然后逆序输出res。求大佬解答，这样为啥会有问题

发表于 2025-03-04 22:23:50 回复(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)