Schedule
http://acm.hdu.edu.cn/showproblem.php?pid=6180
题意：已知一些任务的开始时间和结束时间，一台机器同时只能运行一个任务（机器中间不关闭运行），求在使用最少机器工作的前提下机器工作的最短时间
题解： 将开始时间标记为1，结束时间标记为-1。
按照时间大小对这2n2n个时间从小到大排序，然后遍历计算前缀和，当前缀和每次增加1的时候，说明需要新开一台机器才能运行，这样可以寻找到每台机器的开始时间。同理，逆序遍历计算前缀和，可以记录下每一台机器的结束时间。最后把每一台机器的时间相加即可。
参考文章：原博客 简化版
C++版本一
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
ll t,n,m,k,p,u,v;
ll ans,cnt,flag,temp,sum;
int L[N],R[N];
char str;
struct node{
int val,flag;
bool operator <(const node &S)const{
if(val==S.val)
return flag<S.flag;
return val<S.val;
}
}e[N];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&e[2*i-1].val,&e[2*i].val);
e[2*i-1].flag=1;e[2*i].flag=-1;
}
n<<=1;
sort(e+1,e+n+1);
ans=0;
k=0;
for(int i=1;i<=n;i++){
k+=e[i].flag;
if(ans<k){
ans=k;
L[k]=e[i].val;
}
}
ans=0;
k=0;
for(int i=n;i>=1;i--){
k-=e[i].flag;
if(ans<k){
ans=k;
R[k]=e[i].val;
}
}
sum=0;
for(int i=1;i<=ans;i++)
sum+=R[i]-L[i];
cout<<ans<<" "<<sum<<endl;
}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
#include<iostream>
#include<deque>
#include<memory.h>
#include<stdio.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<math.h>
#include<list>
#include<queue>
#include<set>
#define INF (1LL<<62)
#define ll long long int
using namespace std;
//输入挂，不然超时
int Scan(){
int res = 0, flag = 0;
char ch;
if ((ch = getchar()) == '-'){
flag = 1;
}
else if(ch >= '0' && ch <= '9'){
res = ch - '0';
}
while ((ch = getchar()) >= '0' && ch <= '9'){
res = res * 10 + (ch - '0');
}
return flag ? -res : res;
}
struct qujian{
int l;
int r;
}qs[100005];
bool cmp(qujian a,qujian b){
return a.l<b.l;//按照开始时间排序
}
multiset<int> s; //一定要定义在外面，不然超时
int N;
int main()
{
int t=Scan();
while(t--){
N=Scan();
for(int i=0;i<N;i++){
qs[i].l=Scan();
qs[i].r=Scan();
}
sort(qs,qs+N,cmp);
ll ans=0;
s.clear();//s存所有机器的结束时间
for(int i=0;i<N;i++){
// multiset<int>::iterator it=upper_bound(s.begin(),s.end(),qs[i].l);//algorithm的二分超时！要用Set自带的
multiset<int>::iterator it=s.upper_bound(qs[i].l);
if(it==s.begin())//如果比所有都要小，那么只能新开一个机器了
{
ans+=qs[i].r-qs[i].l;//记录答案
s.insert(qs[i].r);
}
else{
it--;//细节
//要把这两句合并，不然超时！这就是传说中的卡常数吗
// ans+=qs[i].l-*it;//空隙部分
// ans+=qs[i].r-qs[i].l;//当前工作的时间
ans+=qs[i].r-*it;
s.erase(it);
s.insert(qs[i].r);
}
}
printf("%d %I64d\n",s.size(),ans);
}
return 0;
}
C++版本三
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug
using namespace std;
typedef long long LL;
const int maxn=200000+50;
struct Node
{
LL x;
int id;
Node() {}
Node(LL x,int id):x(x),id(id) {}
};
LL sum;;
stack<LL> s;
Node a[maxn];
int ans,n,num,cnt;
int cmp(Node a,Node b)
{
if(a.x==b.x) return a.id>b.id;
else return a.x<b.x;
}
void init()
{
ans=0,sum=0,num=0,cnt=0;
while(!s.empty()) s.pop();
}
int main()
{
#ifdef debu
freopen("1010.in","r",stdin);
#endif // debug
int t;
scanf("%d",&t);
while(t--)
{
init();
scanf("%d",&n);
for(int i=0; i<n; i++)
{
LL l,r;
scanf("%lld%lld",&l,&r);
a[cnt++]=Node(l,0);
a[cnt++]=Node(r,1);
sum+=r-l;
}
sort(a,a+cnt,cmp);
for(int i=0; i<cnt; i++)
{
if(a[i].id==0)
{
num++;
if(!s.empty())
{
LL pre=s.top();
s.pop();
sum+=a[i].x-pre;
}
}
else
{
num--;
s.push(a[i].x);
}
ans=max(ans,num);
}
printf("%d %lld\n",ans,sum);
}
return 0;
}
查看6道真题和解析