【2017 Multi-University Training Contest - Team 10】Schedule
10 2017 multi Contest Training Team Schedule University
2023-09-14 09:03:49 时间
【链接】http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1010&cid=767
【题意】
给一些区间,每台机器在这些区间中运行,但是,一台机器最多只能在一段区间内运行,(在相同的地方有多个区间则需要多个机器),并且,机器关掉不能再开,求:使用最少机器的情况下的最短运行时间。
运行时间是所有机器的运行时间的总和.
【题解】
因为优先的是最小的机器个数;
先将区间按左端点升序排一下.
然后按顺序枚举区间.
对于遇到的区间
要用哪一个机器来处理它呢?
当然是结束时间最晚且在这个区间的左边的机器.
这样的话,每次增加的时间就是最少的了;
而那些结束时间早的,就先尽量不用.
因为用那些的话,增加的时间更多.
如果没有机器可以用的话,那就只好用一台新的机器了
这样的过程可以保证用的机器是最少的。
因为都尽量用了
写个multiset存一下每个机器结束的时间就好.
新加的机器,就假设它是在区间开始的时刻才开动就好.
注意机器是关闭了就不能开启了.所以得一直开着,就算中间没有在做事情。
千万不要用upper_bound(set.begin(),set.end(),a[i])这样的写法。
要这样写
set.upper_bound(a[i]);
不然会超时的!!!
【错的次数】
1
【反思】
1.set.upper_bound(a[i]);
2.要注意看题目
【代码】
#include <cstdio> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <iomanip> #include <set> #include <cstdlib> #include <cmath> using namespace std; #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define LL long long #define rep1(i,a,b) for (int i = a;i <= b;i++) #define rep2(i,a,b) for (int i = a;i >= b;i--) #define mp make_pair #define pb push_back #define fi first #define se second #define ms(x,y) memset(x,y,sizeof x) #define ri(x) scanf("%d",&x) #define rl(x) scanf("%lld",&x) #define rs(x) scanf("%s",x) #define oi(x) printf("%d",x) #define ol(x) printf("%lld",x) #define oc putchar(' ') #define os(x) printf(x) #define all(x) x.begin(),x.end() #define Open() freopen("F:\\rush.txt","r",stdin) #define Close() ios::sync_with_stdio(0) typedef pair<int, int> pii; typedef pair<LL, LL> pll; const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 }; const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 }; const double pi = acos(-1.0); const int N = 1e5; multiset <int> myset; pii a[N + 10]; int n; LL ans = 0; int main() { //Open(); //Close(); int T; ri(T); while (T--) { ri(n); rep1(i, 1, n) ri(a[i].fi), ri(a[i].se); sort(a + 1, a + 1 + n); myset.clear(); LL ans = 0; rep1(i, 1, n) { auto temp = myset.upper_bound(a[i].fi); //cout <<"i="<<i<<' ';cout << (*temp) << endl; if (temp == myset.begin()) { myset.insert(a[i].se); ans = (ans + a[i].second - a[i].first); continue; } temp--; ans = (ans + a[i].second - *temp); myset.erase(temp); myset.insert(a[i].se); } oi((int)myset.size()); oc; ol(ans); puts(""); } return 0; }
相关文章
- 判断一个小时之内是否重复发送了10次短信
- 小白学 Python 数据分析(10):Pandas (九)数据运算
- Kotlin 朱涛-10 泛型 型变 逆变 in 协变 out 星投影
- windows 10 1709精简版安装 Microsoft Store
- 安卓逆向10-ida,动态调试
- 嵌入式新闻早班车-第10期
- java DefaultMutableTreeNode 树形结构 目录 1. Tree的概念1 1.1. treeNode接口,mutabletreenode接口1 1.2. 10-4:以T
- atitit.Oracle 9 10 11 12新特性attilax总结
- 【2017 Multi-University Training Contest - Team 10 】Monkeys
- Windows 10下安装Docker Desktop
- AI:2020年6月23日北京智源大会演讲分享之AI创业专题论坛——10:30-11:20陆奇教授《AI创业发展趋势:机会与挑战》
- 【人工智能AI2.0】清华发布了 ChatGLM-6B & 中国大模型5支学术界团队和10大产业界力量介绍
- 10 - vulhub - Adobe ColdFusion 反序列化漏洞 (CVE-2017-3066)