今天有事要回成都,做的东西不多!
  1. 复习下贪心算法[拟阵和应用],主要是对经典的任务调度有点忘了!等下会在电脑上写下O(N^2)和O(NlogN)的实现,并且补录到算法导论上![个人觉得并查集的思路很巧妙,也很简单;O(N^2)的算法,主要是在边界情况考虑下要异常小心,要注意及时任务的边界不能被破坏,并且要意识到已经存在的边界[0…k-1]是W权重非递增序排列的]

实现代码:

//O(N^2) implementation
int GreedyJob(int n){
    int i,j,k,sum=0;
    //find the second item
    k=1,J1[1]=1;
    for(i=2; i<=n; i++){
        j=k;
        while(d[J1[j]]>d[i]&&d[J1[j]]!=j) j–;//not-last on-time job
        if(d[J1[j]]<=d[i]&&d[i]>j){//take care of d[i]>=j+1, target position is j+1
            for(int m=k; m>j; m–) J1[m+1]=J1[m];
            J1[j+1]=i;
            k++;
        }
        else sum+=w[i];
    }
    #ifdef test
    for(i=1; i<=k; i++) cout<<J1[i]<<" ";
    cout<<endl<<sum<<endl;
    #endif
    return k;
}

int FastJob(int n){
    int i,j,k=1,t,sum=0;
    UFS u;
    int *F=new int[n+1];
    for(i=0; i<=n; i++){u.MakeSet(i);F[i]=i;}
    for(i=1; i<=n; i++){
        j=n<d[i]?u.Find(n):u.Find(d[i]);
        if(F[j]>0){
            J2[k++]=i;
            u.Union(F[j]-1, F[j]);
            F[j]=F[j]-1;
        }
        else sum+=w[i];
    }
    #ifdef test
    for(i=1; i<k; i++) cout<<J2[i]<<" ";
    cout<<endl<<sum<<endl;
    #endif
    return k;
}

让我异常生气地是,UFS写了一万遍了,居然还犯老毛病,明早重新写一个,找生成树来试验!如果没一次过,就天天写一次,直到一次过为止!

#ifndef UNIONFINDSET_H_INCLUDED
#define UNIONFINDSET_H_INCLUDED
#include <limits.h>
const int MaxUFS=200;

class UFS{
public:
    UFS(){//intialize p with each item INT_MAX
        for(int i=0; i<MaxUFS; i++) p[i]=INT_MAX;
    }
    bool MakeSet(int v){
        if(v<0||p[v]!=INT_MAX) return false;
        return p[v]=-1;//intialization, p[v]=-1, if it’s non-zero, 1
    }

    int Find(int v){
        if(v<0||p[v]==INT_MAX) return -1;//no represstative item
        int f=v;
        while(p[f]>=0) f=p[f];
        while(v!=f){//v!=f serve bugs,Orlando出离愤怒,这块老是要写成p[v]!=f,真的是瓜!v==f时,天上去找p[v]==f哟,生气,太不争气了!
            int tmp=p[v];
            p[v]=f;
            v=tmp;
        }
        return f;
    }

    bool Union(int u, int v){
        if(u<0||v<0||p[u]==INT_MAX||p[v]==INT_MAX) return false;
        int t1=Find(u), t2=Find(v);
        int p1=p[t1], p2=p[t2];
        if(p1<=p2){
            p[t2]=t1;
            p[t1]=p1+p2;
        }
        else{
            p[t1]=t2;
            p[t2]=p1+p2;
        }
        return true;
    }
private:
    int p[MaxUFS];
};

#endif // UNIONFINDSET_H_INCLUDED

  1. C++编程规范:16,24宏的利用,总之,“Macro is evil, if out of control!”OK!
    • 只有在条件编译,外部文件处理和assert实现时,才使用宏!
    • 条件编译模板

#define XXX

#ifdef XXX

#endif

#undef XXX //很重要的,不要让你的宏定义流出

    • 引用外部头文件时,宏应该如何编写呢?
    1. 过时且存在问题的模板

#ifndef XXX

#include "foo.h"

#define XXX

#endif//看出问题没有,调用方和头文件的保护符名称存在潜在不一致

     2,    请使用如下模板:


#ifndef XXX

#define XXX //调用方的宏

#include "foo.h"

#endif

    • 很不好意思写在这里,搜索部分一直没动,只有晚上看能不能理解了!最难的部分来了,加油!呵呵,决定把贪心的练习和搜索同时开始,贪心总是让人心情愉快,哈哈
Advertisements