防晒
题意
有 C 头奶牛进行日光浴，第 i 头奶牛需要 minSPF[i] 到 maxSPF[i] 单位强度之间的阳光。
每头奶牛在日光浴前必须涂防晒霜，防晒霜有 L 种，涂上第 i 种之后，身体接收到的阳光强度就会稳定为 SPF[i]，第 i 种防晒霜有 cover[i] 瓶。
求最多可以满足多少头奶牛进行日光浴。
思路
刚拿到这题的时候，我也不知道应该按什么顺序排序，但是我知道要么是按照 minSPF递增排序，要么是按照 maxSPF 递减排序。那么我们假设按照 maxSPF 递增排序。
如下图，有两头牛的 minSP 和 maxSPF 的范围和两种不同的防晒霜 x y
那么我们应该把较大的 x 还是较小的 y 分配给第 i 头牛呢？
我们先假设 x 和 y 都可以分配给 第 i 头牛，因为我们是按照maxSPF递增排序的 所以第 i + 1头牛的maxSPF 一定大于等于第 i 头牛的maxSPF，那么值越大的防晒霜越有可能让更多的牛使用，所以当前第 i 头牛选择它能使用的值最小的防晒霜。
按照 minSPF递减排序也是一样的道理。
值越小的防晒霜越有可能让更多的牛使用，所以选择当前牛能选择的值最大的防晒霜。
代码
下面提供按照 maxSPF递增排序的参考代码。
#include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define mod 1000000007 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) using namespace std; typedef long long LL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } const int N = 2600; int c, L; struct Node { int l, r; bool operator<(Node& x)const { return r < x.r; } }node[N]; struct Node1 { int spf; int cover; bool operator<(Node1& x)const { return spf < x.spf; } }node1[N]; void solve() { cin >> c >> L; for (int i = 1; i <= c; ++i) { cin >> node[i].l >> node[i].r; } for (int i = 1; i <= L; ++i) { cin >> node1[i].spf >> node1[i].cover; } sort(node + 1, node + 1 + c); sort(node1 + 1, node1 + 1 + L); int res = 0; for (int i = 1; i <= c; ++i) { for (int j = 1; j <= L; ++j) { if (node1[j].spf >= node[i].l && node1[j].spf <= node[i].r && node1[j].cover) { node1[j].cover--; res++; break; } } } cout << res << endl; } signed main() { // int t; cin >> t; // while (t--) solve(); return 0; }
