字节跳动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;
    }


全部评论

相关推荐

头像
11-09 17:30
门头沟学院 Java
TYUT太摆金星:我也是,好几个华为的社招找我了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务