TIOJ 1130 Dark Kingdom II [Greedy]

poao899    228K    546MS    G++     0.81K     2010-03-28 15:22:42                            .

奇怪最近寫一大堆Greedy


是說我無法證明這是正確的耶zzz

只是覺得超合理   寫起來超毛的











而且看著大家的code length 好像只有我有co     Heap          耶Q

//**************************

#include<algorithm>
int n, m, st[30000], ed[30000], c1, c2, top;
int main(){
    while(~scanf("%d%d",&n,&m)){
        c1=c2=0; top=m;
        for(int i=0; i<m; i++){
            scanf("%d%d", st+i, ed+i);
            c1+= (st[i]>ed[i]? ed[i]+n-st[i]: ed[i]-st[i]);
        }
        std::sort(st, st+m);
        for(int i=0; i<m; i++){
            if(ed[i]< st[0])
                ed[i]+= n;
            ed[i]= -ed[i];
        }
        std::make_heap(ed, ed+top);
        for(int i=0; i<m; i++){
            while(-ed[0]< st[i]){
                std::pop_heap(ed, ed+top--);
                ed[top]-= n;
                std::push_heap(ed, ed+top++);
            }
            c2+= -ed[0]-st[i];
            std::pop_heap(ed, ed+top--);
        }
        printf("%d\n", c1-c2);
    }
}