d555 - 平面上的極大點
題目描述
題目要求找出平面上給定點集合的極大點集合。一個點 (x, y) 支配另一個點 (a, b) 如果 x >= a 且 y >= b。極大點是指不會被集合中其他點支配的點。
解題思路
首先，按照 y 座標降序，x 座標升序對點進行排序。然後，使用貪心策略遍歷排序後的點。維護一個 sx 和 sy，分別表示目前找到的極大點的 x 座標和 y 座標的上限。對於每個點，如果它的 y 座標小於 sy 且 x 座標大於 sx，則將其添加到極大點集合中，並更新 sx 和 sy。這樣可以確保找到的點不會被其他點支配。
複雜度分析
- 時間複雜度: O(n log n)，主要來自排序操作。遍歷點集合的時間複雜度為 O(n)，但排序佔主導地位。
- 空間複雜度: O(n)，用於儲存點集合。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
struct p{
int x;
int y;
};
bool cmp(p a,p b){
if(a.y>b.y)
return 1;
else if(a.y==b.y&&a.x>b.x)
return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,ca=0;
while(cin >> n){
p a[n];
int sx=-1,ans=0,sy=100001;
for(int i=0;i<n;++i)
cin >> a[i].x >> a[i].y;
sort(a,a+n,cmp);
for(int i=0;i<n;++i){
if(a[i].y<sy&&a[i].x>sx){
sx=a[i].x;
sy=a[i].y;
++ans;
}
}
cout << "Case " << ++ca << ":\nDominate Point: " << ans << "\n";
sx=-1;sy=100001;
for(int i=0;i<n;++i){
if(a[i].y<sy&&a[i].x>sx){
sx=a[i].x;
sy=a[i].y;
cout << "(" << a[i].x << "," << a[i].y << ")\n";
}
}
}
}