Solutions of Segment

Select solution language

sharinganvanhoadong Created at 1 likes

#**HƯỚNG DẪN:**<br> - Bắt đầu chọn dãy các đoạn thẳng từ đoạn đầu tiên bên trái, thực hiện ghép các đoạn nối tiếp vào bên trái đoạn này. Khi đó cần đoạn đó kéo đến vị trí càng bé càng tốt.(để chừa chỗ cho các đoạn khác)<br> - Do đó ta sort các đoạn tăng dần theo vị trí kết thúc của mỗi đoạn. (ta chỉ cần quan tâm đoạn đó kéo đến vị trí càng bé càng tốt và xuất phát từ vị trí không bị có điểm trùng với đoạn đằng trước.<br> - Dùng $1$ biến đánh dấu vị trí kết thúc của đoạn trước, nếu đoạn sau mà có vị trí bắt đầu lơn hơn vị trí kêt thúc thì thêm đoạn vào dãy. ##**CODE MẪU:** ```cpp #include<iostream> #include<algorithm> using namespace std; int n,dd,ans; pair<int,int> a[100005]; bool cmp(pair<int,int> a,pair<int,int>b) { return a.second<b.second; } int main() { cin>>n; for(int i=0;i<n;i++) { cin>>a[i].first>>a[i].second; } sort(a,a+n,cmp); for(int i=0;i<n;i++) { if(a[i].first>dd) ans++,dd=a[i].second; } cout<<ans; } ```