ZOJ 3717: Final Exam Arrangement

タイトルリンク:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3721
タイトル:
いくつかのカリキュラムの授業区間を提供し、
2つのカリキュラムの授業時間が重複しなければ、この2つのカリキュラムを同時に選択する学生がいる可能性があるため、1日の試験に手配することはできません.
少なくとも何日の試験を手配して、そして方案を出力します
アルゴリズム:
セグメントツリー最適化DP
まず、授業を終了時間に並べ替えます.
1つのコースでは、
すべての終了時間の開始時間より前のコース(つまり交差しないコース)を処理します.
それらの試験日が最も遅い日を求めて、それからこの日を+1して、この現在処理しているこの課程の最も早い試験時間を得ました.
すべての授業は最初の試験時間に従って試験され、総試験時間は最も短くなります.
実はこの解の過程の証明は特に厳格ではありませんて、もっと厳格な証明があることを期待します.
コードは次のとおりです.

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<sstream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<queue>
#include<vector>
#include<stack>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define eps 1e-8
using namespace std;
typedef pair<int,int> PII;

const int MAXN=300000;
int s[MAXN],t[MAXN];
int tr[MAXN<<2];
vector<int> hash;
vector<int> ans[MAXN];
vector<pair<PII,int> > a;

int query(int l, int r, int L, int R, int rt) {
    if(L<=l&&r<=R) {
        return tr[rt];
    }
    int mid=(l+r)>>1;
    int tmp=0;
    if(L<=mid) {
        tmp=max(tmp,query(l,mid,L,R,rt<<1));
    }
    if(R>mid) {
        tmp=max(tmp,query(mid+1,r,L,R,rt<<1|1));
    }
    return tmp;
}

void update(int l, int r, int x, int c, int rt) {
        tr[rt]=max(tr[rt],c);
        if(l==r) {
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid) {
        update(l,mid,x,c,rt<<1);
    } else {
        update(mid+1,r,x,c,rt<<1|1);
    }
}

int main() {
    int n;
    while(scanf("%d",&n)==1) {
        hash.clear();
        a.clear();
        for(int i=1; i<=n; i++) {
            ans[i].clear();
        }
        for(int i=1; i<=n; i++) {
            scanf("%d%d",&s[i],&t[i]);
            hash.push_back(s[i]);
            hash.push_back(t[i]);
            a.push_back(make_pair(make_pair(t[i],s[i]),i));
        }
        sort(hash.begin(),hash.end());
        hash.erase(unique(hash.begin(),hash.end()),hash.end());
        sort(a.begin(),a.end());
        int m=hash.size();
        memset(tr,0,sizeof(tr));
        for(int i=0; i<n; i++) {
            a[i].first.second=lower_bound(hash.begin(),hash.end(),a[i].first.second)-hash.begin();
            a[i].first.first=lower_bound(hash.begin(),hash.end(),a[i].first.first)-hash.begin();
        }
        int num=1;
        for(int i=0; i<n; i++) {
            int tmp=query(0,m-1,0,a[i].first.second,1)+1;
            num=max(num,tmp);
            ans[tmp].push_back(a[i].second);
            update(0,m-1,a[i].first.first,tmp,1);
        }
        printf("%d
",num);
        for(int i=1; i<=num; i++) {
            sort(ans[i].begin(),ans[i].end());
            for(int j=0; j<ans[i].size(); j++) {
                if(j) {
                    printf(" ");
                }
                printf("%d",ans[i][j]);
            }
            puts("");
        }
    }
    return 0;
}