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