首页 / MAC / 雅礼培训day2 时间机器 machine

雅礼培训day2 时间机器 machine

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了雅礼培训day2 时间机器 machine，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1662字，纯文字阅读大概需要3分钟。

内容图文

技术分享 技术分享 技术分享

题目大意：

给你两组区间，求覆盖问题。

对于这个问题我们可以针对每个区间的左端点进行排序，在枚举节点时，在左端点满足要求的情况下，是使右端点尽量靠近节点的右端点，使用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(){
10char c = getchar();
11while(c < ‘0‘ || c > ‘9‘) c = getchar();
12int x = c - ‘0‘;
13     c = getchar();
14while(c <= ‘9‘ && c >= ‘0‘) x = x * 10 + c - ‘0‘, c = getchar();
15return x;
16}
1718constint N = 100010;
1920usingnamespace std;
2122 typedef longlong LL;
2324 map<int, LL> M;
25 typedef map<int, LL>::iterator it;
2627struct Node{
28int l, r, s;
2930booloperator < (const Node& B) const{
31return l < B.l;
32    }
33}A[N], R[N];
3435 inline void Add(int u, int s){
36if(!M.count(u)) M[u] = s;
37else M[u] += s;
38}
3940int n, m;
4142void check(){
43int j = 1;
44     For(i, 1, n){
45while(j <= m && R[j].l <= A[i].l) Add(R[j].r, R[j].s), ++j;
46while(A[i].s){
47             it p = M.lower_bound(A[i].r);
48if(p == M.end()){
49                 puts("No");
50return;
51            }
52if(A[i].s < p -> y) p -> y -= A[i].s, A[i].s = 0;
53else A[i].s -= p -> y, M.erase(p);
54        }
55    }
56     puts("Yes");
57}
5859int main(){
60     freopen("machine2.in", "r", stdin);
61     freopen("machine2.ans", "w", stdout);
62int Case = Read();
63while(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    }
71return0;
72 }

 

原文：http://www.cnblogs.com/xxjnoi/p/7277245.html

内容总结

以上是互联网集市为您收集整理的雅礼培训day2 时间机器 machine全部内容，希望文章能够帮你解决雅礼培训day2 时间机器 machine所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1263665.html

来源：【匿名】