编程题1

#include<bits/stdc++.h>
using namespace std;

const int maxn=5e5+5;

struct point
{
    int x;
    int y;
}p[maxn],ans[maxn];

bool cmpMaxtoMin(point a,point b)
{
    if(a.x==b.x)
        return a.y>b.y;
    return a.x>b.x;
}

bool cmpMintoMax(point a,point b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d%d",&p[i].x,&p[i].y);
        
    sort(p+1,p+1+n,cmpMaxtoMin);
    
    int len=0,max_y=-1;
    for(int i=1;i<=n;++i)
        if(p[i].y>max_y)
            ans[len++]=p[i],max_y=p[i].y;
    
    sort(ans,ans+len,cmpMintoMax);
    for(int i=0;i<len;++i)
        printf("%d %d\n",ans[i].x,ans[i].y);
    return 0;
}

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])

N=eval(input())
xy=[]  for i in range(N):
    x,y=map(int,input().split())    xy.append((x,y))
g=[x for x in xy]   for i in range(len(xy)):
    a,b=xy[i]  for j in range(len(xy)):  if xy[j][0] > a and xy[j][1]>b:
            g.remove((a,b)) break b=sorted(g,key=lambda k: k[1],reverse=True)  for i in range(len(b)):  print(b[i][0],b[i][1])

这个网站上的有问题,亲自实践无论是他给出的5个坐标,还是10个坐标,我写的程序都没有错误,但是他却提示结果判断错误

#include<iostream>
#include<algorithm>
using namespace std;

struct point{
    int x, y;
};

bool cmp(point a, point b)
{
    return a.x>b.x;
}
int main()
{
    int N;
    cin>>N;
    point p[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, cmp);
    int len = 1;
    int curY = p[0].y;
    for(int i=1; i<N; ++i)
    {
        if(p[i].y>curY)
        {
            curY = p[i].y;
            p[len].x = p[i].x;
            p[len].y = p[i].y;
            ++len;
        }
    }
    for(int i=len-1; i>=0; --i)
        printf("%d %d\n", p[i].x, p[i].y);
    return 0;
}

使用cin cout时间运行通不过

70%超时。。求大佬们提意见～～啥意见都行

import java.util.*; 
public class Main { 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); int num = Integer.valueOf(scanner.nextLine());
        Point[] points = new Point[num];
        List maxPoints = new ArrayList();
        String[] line; for (int i = 0; i < num; i++) {
            line = scanner.nextLine().trim().split(" ");
            points[i] = new Point(Integer.valueOf(line[0]), Integer.valueOf(line[1]));
        }
        Arrays.sort(points);
        maxPoints.add(points[num - 1]); 
        int maxY = points[num - 1].y; for (int i = num - 2; i >= 0; i--) { if (points[i].y >= maxY) {
                maxPoints.add(points[i]);
                maxY = points[i].y;
            }
        }
        Collections.reverse(maxPoints);
        maxPoints.forEach(System.out::println);
    } 
    static class Point implements Comparator<Point> { 
        int x; 
        int y; 
        public Point(int x, int y) { 
            this.x = x; this.y = y;
        } 
        [@Override](/profile/992988)  
        public int compareTo(Point o) { 
            return Integer.compare(this.x, o.x);
        } 
        [@Override](/profile/992988)  
        public String toString() { 
            return x + " " + y;
        }
    }
}

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])
        

分析：

• 1.对 X进行排序
• 2.按照 X从大到小遍历所有的点, 判断当前的 Y是否大于最大 Y, 如果大于, 则是最大点, 保存到数组中.
• 3.最后倒序输出数组

不能完全 AC的原因：
尽量使用 scanf/printf函数, 效率要比 cin/cout高

#include 
using namespace std;
#define nullptr NULL

struct Point {
    int x;
    int y;
};

// 比较器, 按 X降序 
bool cmp(const Point a, const Point b) {
    return a.x > b.x;
}

int main()
{
    int n;
    cin >> n;
    Point point[n];
    int x, y;
    for(int i = 0; i < n; i++) {
      scanf("%d%d", &x, &y);
      point[i].x = x;
      point[i].y = y;
    }
    //排序
    sort(point, point + n, cmp);
     // 找出最大点 
    int len = 1;
    int curY = point[0].y;
    for(int i = 1; i < n; i++) {
        if(point[i].y > curY) {        // 这里取不取等都可以 AC 
            curY = point[i].y;
            point[len].x = point[i].x;
            point[len].y = point[i].y;
            len++;
        }
    }
    for(int i = len - 1; i >= 0; i--) {
         printf("%d %d\n", point[i].x, point[i].y);
    }
    return 0;
}

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])

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])