字节跳动ZJ13->最大点集

最大点集

http://www.nowcoder.com/questionTerminal/089dbc5ec7ac468589ce143d43248949

1. 思路

  1. 想法是反向思考 把不符合条件的都去掉就好了,emmm但是不太好整(原思路:找出最大的x,将y小于他的全部去掉。然后找出y最大的,再将x<他的全去掉)emmmm跑出来发现不中 哈哈哈,但是这边结构体和sort排序挺好的
  2. 排序用法:自己指定一个比较函数。通过sort的第三个参数传进去。

2.初级代码

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

    struct P{
        int x=0, y=0,flag=1;

    }; 
    bool comparex(const P &a, const P &b) {//让x从小到大排序 
        return a.x < b.x;
    }
     bool comparey(const P &a, const P &b) {//让x从小到大排序 
        return a.y < b.y;
    }
    int main(){
    int n, x, y, Max=0;
    scanf("%d", &n);
    P p[n];
    for(int i=0;i<n;i++)
        cin>> p[i].x>> p[i].y;
    sort(p, p+n,comparey);//x 
    for(int i=0;i<n-1;i++){
        if(p[i].x < p[n-1].x)
            p[i].flag=0;
    }
        sort(p, p+n,comparex);//x 
    for(int i=0;i<n-1;i++){
        if(p[i].y < p[n-1].y)
            p[i].flag=0;
    }
    for(int i=0;i<n-1;i++){
        if(p[i].flag==1)
            cout<<p[i].x<<" "<<p[i].y<<endl;
    }
    return 0;
}

3. 正解参考

1) 思路是先将y从大到小排序
2) y定好了之后,由于y牟定了高度,只要下一个x不比出现过的x小就绝对没问题,所以设立一个Max=0;进行控制。而且也能使x递增。非常好用。

#include <bits/stdc++.h>
using namespace std;
    struct P{
        int x=0, y=0;

    }; 
     bool comparey(const P &a, const P &b) {//让y从大到小排序 
        return a.y > b.y;
    }
    int main(){
    int n, x, y, Max=0;
    cin>>n;
    P p[n];
    for(int i=0;i<n;i++)
        cin>> p[i].x>> p[i].y;
    sort(p, p+n,comparey);//x 
    for(int i=0;i<n;i++){
            if(p[i].x>Max){
                Max=p[i].x;
                cout<<p[i].x<<" "<<p[i].y<<endl;
            }
        }
        return 0;
    }


注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议