传送门 UVa 11020
m u l t i s e t multiset multiset 维护每次更新后的 e f f i c i e n t g r o o m s efficient\ grooms efficient grooms，可以发现 C / L C/L C/L 随着 L / C L/C L/C 递增而递减，且对于每一个 C / L C/L C/L 值，有唯一的 L / C L/C L/C 与其对应；则 m u l t i s e t multiset multiset 可以先对 C / L C/L C/L 排序再按 L / C L/C L/C 排序。那么当前遍历的 g r o o m groom groom 是否可以加入 m u l t i s e t multiset multiset 取决于是否满足上述递减性质；若可以加入，则要删除 m u l t i s e t multiset multiset 中地位比其低的元素。
#include <bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f #define maxn 15005 typedef pair<int, int> P; int t, n; int main() { scanf("%d", &t); for (int i = 1; i <= t; i++) { printf("Case #%d:\n", i); multiset<P> st; scanf("%d", &n); while (n--) { int a, b; scanf("%d%d", &a, &b); P p = P(a, b); multiset<P>::iterator it = st.lower_bound(p); if (it == st.begin() || (*(--it)).second > b) { it = st.upper_bound(p); while (it != st.end() && (*it).second >= b) it = st.erase(it); st.insert(p); } printf("%d\n", (int)st.size()); } if (i != t) putchar('\n'); } return 0; }