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 DEBUGfreopen("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 DEBUGprintf("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 debufreopen("1010.in","r",stdin); #endif // debugint 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; }

?

總結

以上是生活随笔為你收集整理的Schedule的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。