字节跳动ZJ13->最大点集
最大点集
http://www.nowcoder.com/questionTerminal/089dbc5ec7ac468589ce143d43248949
1. 思路
- 想法是反向思考 把不符合条件的都去掉就好了,emmm但是不太好整(原思路:找出最大的x,将y小于他的全部去掉。然后找出y最大的,再将x<他的全去掉)emmmm跑出来发现不中 哈哈哈,但是这边结构体和sort排序挺好的
- 排序用法:自己指定一个比较函数。通过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;
}

查看9道真题和解析