【链接】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;
}