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

}

巴特西

【2017 Multi-University Training Contest - Team 10】Schedule