本文共 1861 字，大约阅读时间需要 6 分钟。
题目大意：
给你两组区间，求覆盖问题。
对于这个问题我们可以针对每个区间的左端点进行排序，在枚举节点时，在左端点满足要求的情况下，是使右端点尽量靠近节点的右端点，使用map来优化
代码送上：
1 #include 2 #include 3 #include 4 5 #define For(i, j, k) for(int i = j; i <= k; i++) 6 #define y second 7 8 9 inline int Read(){10 char c = getchar();11 while(c < '0' || c > '9') c = getchar();12 int x = c - '0';13 c = getchar();14 while(c <= '9' && c >= '0') x = x * 10 + c - '0', c = getchar();15 return x;16 }17 18 const int N = 100010;19 20 using namespace std;21 22 typedef long long LL;23 24 map M;25 typedef map ::iterator it;26 27 struct Node{28 int l, r, s;29 30 bool operator < (const Node& B) const{31 return l < B.l;32 }33 }A[N], R[N];34 35 inline void Add(int u, int s){36 if(!M.count(u)) M[u] = s;37 else M[u] += s;38 }39 40 int n, m;41 42 void check(){43 int j = 1;44 For(i, 1, n){45 while(j <= m && R[j].l <= A[i].l) Add(R[j].r, R[j].s), ++j;46 while(A[i].s){47 it p = M.lower_bound(A[i].r);48 if(p == M.end()){49 puts("No");50 return;51 }52 if(A[i].s < p -> y) p -> y -= A[i].s, A[i].s = 0;53 else A[i].s -= p -> y, M.erase(p);54 }55 }56 puts("Yes");57 }58 59 int main(){60 freopen("machine2.in", "r", stdin);61 freopen("machine2.ans", "w", stdout);62 int Case = Read();63 while(Case--){64 M.clear();65 n = Read(), m = Read();66 For(i, 1, n) A[i].l = Read(), A[i].r = Read(), A[i].s = Read();67 For(i, 1, m) R[i].l = Read(), R[i].r = Read(), R[i].s = Read();68 sort(A + 1, A + n + 1), sort(R + 1, R + m + 1);69 check();70 }71 return 0;72 }
转载于:https://www.cnblogs.com/xxjnoi/p/7277245.html
