首页 > 代码库 > 雅礼培训day2 时间机器 machine
雅礼培训day2 时间机器 machine
题目大意:
给你两组区间,求覆盖问题。
对于这个问题我们可以针对每个区间的左端点进行排序,在枚举节点时,在左端点满足要求的情况下,是使右端点尽量靠近节点的右端点,使用map来优化
代码送上:
1 #include <cstdio> 2 #include <algorithm> 3 #include <map> 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<int, LL> M; 25 typedef map<int, LL>::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 }
雅礼培训day2 时间机器 machine
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。