ACM笔记之贪心

区间最大点覆盖问题

用点最多能覆盖多少个区间，一个点最多只能覆盖一个区间 Q：给定n个区间和m个点，一个点最多只能使用一次，询问最多有多少个区间可以被点覆盖到？ A：首先按照区间左端点从小到大排序，点也按照从小到大排序，反向枚举每个区间，在此基础上再反向枚举点，如果这个点在区间中，那么答案加1，统计完就是最终答案。算法时间复杂度为 $O(n^2)$ 优化：利用upper_bound $O(logn)$得到第一个大于区间右端点的点，再自减（要加哨兵）就是第一个小于等于区间右端点的点，如果这个点同时又满足大于区间左端点，就让答案加1，算法时间复杂度为 $O(nlongn)$

例如：Acwing 110

#include<bits/stdc++.h> using namespace std; const int N = 2505; typedef pair<int,int> PII; PII cow[N]; //区间(第一关键字为左端点，第二为右端点),点(点的值，点的数目) int n,m; int main() { cin >> n >> m; map<int,int>mp; for(int i = 0; i < n; ++ i) { cin >> cow[i].first >> cow[i].second; } sort(cow, cow + n); for(int i = 0 ,x, y; i < m; ++ i) { cin >> x >> y; mp[x] += y; } int cnt = 0; mp[0] = mp[1001] = n; for(int i = n - 1; i >= 0; -- i) { auto it = mp.upper_bound(cow[i].second); --it; if(it->second > 0 && it->first >= cow[i].first) { ++cnt; if(--it->second == 0) mp.erase(it); } } cout << cnt << endl; }

最大带点权二分图匹配问题

Q：给定两组点设为组A，B，每组点都有两个参数x和y，一组中的某个点 a（属于A） 只能和另一组的某个点 b（属于B） 匹配（当且仅当 a 的两个参数都大于 b），若匹配成功b会得到一定的回报，不能重复匹配，询问最大的匹配数？在此基础上询问最大的权值 A：一般最大带边权匹配问题用KM算法（要求是完全匹配），最大带点权问题用匈牙利算法。而此题可以利用参数的性质贪心，将两个参数以x为第一关键字，y为第二关键字从大到小排序，然后从前往后枚举能获得回报的那组点（组B），利用mutiset维护符合x上匹配条件的组A中的点，每次选择大于等于yb的那个点就是最优算法。

Acwing127

#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; struct Machine { int x,y; bool operator < (const Machine &p)const { return x > p.x || (x==p.x && y>p.y); } }A[N]; struct task { int x,y; bool operator < (const task &p)const { return x > p.x || (x==p.x && y>p.y); } }B[N]; int n,m; int main() { while(cin >> n >> m) { for(int i = 0; i < n; ++ i) { cin >> A[i].x >> A[i].y; } for(int i = 0; i < m; ++ i) { cin >> B[i].x >> B[i].y; } sort(A,A+n); sort(B,B+m); multiset<int>set; int cnt = 0; long long sum = 0; for(int i = 0, j = 0; i < m; ++ i) { while(j < n && A[j].x >= B[i].x) set.insert(A[j++].y); auto it = lower_bound(set.begin(),set.end(),B[i].y); if(it != set.end()) { ++cnt, sum+= B[i].x * 500 + B[i].y * 2; set.erase(it); } } cout << cnt << " " << sum << endl; } return 0; }

区间合并问题

Q：给定n个区间，询问最少可以合并成多少个区间，两个区间能合并当且仅当区间没有交集（包括端点）。 A：贪心，算法的时间复杂度为$O(nlogn)$ 1.按区间左端点排序 2.用小根堆维护当前区间最后一个区间的右端点，即最小的右端点 3.从前往后枚举区间，如果当前区间的左端点小于最小的右端点，说明要新加一个区间，否则直接更新最小右端点即可。

Acwing 111

/* 类似区间合并 */ #include<bits/stdc++.h> using namespace std; const int N = 5e4+5; typedef pair<int,int> PII; typedef pair<PII,int> PIII; int n; PIII A[N]; int id[N]; struct node{ int val,id; ///区间右端点，组的编号 bool operator < (const node &x)const { return val > x.val; } }; int main() { cin >> n; for(int i=1;i<=n;++i) { cin >> A[i].first.first >> A[i].first.second; ///区间左端点，右端点 A[i].second = i; ///区间原编号 } sort(A+1,A+1+n); ///按照区间左端点排序 int ans = 0; priority_queue<node>q; ///重载小根堆 for(int i=1;i<=n;++i) { if(q.empty() || A[i].first.first <= q.top().val ) { q.push({A[i].first.second,++ans}); id[A[i].second] = ans; } else { int idx = q.top().id; q.pop(); q.push({A[i].first.second,idx}); id[A[i].second] = idx; } } cout << ans << endl; for(int i=1;i<=n;++i) cout << id[i] << endl; }

雷达问题

最少用多少个点能覆盖全部区间，一个点可以同时覆盖多个区间

思路： 1.先求每个点能被探测到的雷达放置区间 2.按照右端点从小到大排序 3.从前往后枚举每个区间，如果当前区间包含最后一个点则继续，否则选取当前区间的右端点作为新的点

#include<bits/stdc++.h> using namespace std; const int N = 1005; typedef pair<double,double> PDD; typedef pair<int,int> PII; int n,d; PII P[N]; PDD A[N]; int x,y; int main() { cin >> n >> d; for(int i=1;i<=n;++i) { cin >> x >> y; if(y>d) { puts("-1"); return 0; } double t = sqrt(d*d - y*y); A[i].first = x+t, A[i].second = x-t; } double k = -DBL_MAX; int ans = 0; sort(A+1,A+1+n); for(int i=1;i<=n;++i) { if(A[i].second <= k) continue; //不用判断k <= A[i].first因为按照 排序就已经是符合此条件了 else { ++ans; k = A[i].first; } } cout << ans << endl; }