goal00001111

     摘要: 快速排序是在实践中最快的已知排序算法，它的平均运行时间是O（NlogN）。该算法之所以特别快，主要是由于非常精练和高度优化的内部循环。在队列中寻找合适的枢点元素，并按枢点元素划分序列，是快速排序算法的关键。
为简单起见，我这里数组的第一个元素作为枢点元素，重新排列数组，使得枢点元素之前的元素都小于枢点元素，而枢点元素之后的元素都大于或等于枢点元素。  阅读全文

     摘要: 排序在最坏的情况下，其时间复杂度也能达到O（nlogn）。相对于快速排序来说，这是它最大的优点，此外，堆排序仅需要一个记录大小供交换用的辅助存储空间。
堆排序的数据结构是二叉堆，二叉堆的特点有两个，一个是它是一棵完全二叉树，另一个是它的根结点小于孩子结点，所以我们很容易找到它的最小结点----根结点；当然如果你想找到最大结点的话，那就要扫描所有的叶子结点，这是很费时间的，如果你想找的是最大结点的话，你最好把它弄成一个大顶堆，即一棵根结点大于孩子结点的完全二叉树。
二叉堆通常用数组来实现，它舍弃下标0，从下标1开始置数，则很容易满足，对于数组中任意位置i上的元素，其左儿子的位置在2i上，右儿子的位置在2i+1上，双亲的位置则在i/2上。
堆排序的算法之一是把数组构建成二叉堆----这只要增添一个长度为n+1的辅助空间，然后把原数组的元素依次插入到二叉堆即可。然后删除二叉堆的根，把它作为排序后的数组的第一个元素,然后使二叉堆的长度减1，并通过上移使得新得到的序列仍为二叉堆，再提取新二叉堆的第一个元素到新数组。依此类推，直到提取最后  阅读全文

/*
问题描述：有三个柱子A, B, C. A柱子上叠放有n个盘子，每个盘子都比它下面的盘子要小一点，
可以从上到下用1, 2, ..., n编号。要求借助柱子B，把柱子A上的所有的盘子移动到柱子C上。
移动条件为：1、一次只能移一个盘子；
2、移动过程中大盘子不能放在小盘子上，只能小盘子放在大盘子上。
*/
/*
递归的算法相信大多数人都知道，非递归算法也有出现过。
如：摘自http://www.programfan.com/club/old_showbbs.asp?id=96548
作者：qq590240
#include <iostream>
#include <stdlib.h>

#ifdef _WIN32
using namespace std;
#endif

static void hanoi(int height)
{
    int fromPole, toPole, Disk;
    int *BitStr = new int[height],
        *Hold   = new int[height];
    char Place[]  = {'A', 'B', 'C'};
    int i, j, temp;

    for (i=0; i < height; i++)
    {
        BitStr[i] = 0;
        Hold[i] = 1;
    }
    temp = 3 - (height % 2);
    int TotalMoves = (1 << height) - 1;
    for (i=1; i <= TotalMoves; i++)
    {
        for (j=0 ; BitStr[j] != 0; j++)
        {
            BitStr[j] = 0;
        }
        BitStr[j] = 1;
        Disk = j+1;
        if (Disk == 1)
        {
            fromPole = Hold[0];
            toPole = 6 - fromPole - temp;
            temp = fromPole;
        }
        else
        {
            fromPole = Hold[Disk-1];
            toPole = 6 - Hold[0] - Hold[Disk-1];
        }
        cout << "Move disk " << Disk << " from " << Place[fromPole-1]
             << " to " << Place[toPole-1] << endl;
        Hold[Disk-1] = toPole;
    }
}

 

int main(int argc, char *argv[])
{
    cout << "Towers of Hanoi: " << endl
         << "moving a tower of n disks from pole A to pole B by using pole C" << endl;
    cout << "Input the height of the original tower: ";
    int height;
    cin >> height;
    hanoi(height);

    system("PAUSE");
    return EXIT_SUCCESS;
}
 ////////////////////////////////////////////////////////////
 我在这里根据《数学营养菜》（谈祥柏 著）提供的一种方法，编了一个程序来实现。
*/
/*
算法介绍：
首先容易证明，当盘子的个数为n时，移动的次数应等于2^n - 1。
一位美国学者发现一种出人意料的方法，只要轮流进行两步操作就可以了。
首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上。
根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
（1）按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；
若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
（2）接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。
即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘
这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
（3）反复进行（1）（2）操作，最后就能按规定完成汉诺塔的移动。
*/
#include <iostream>
using namespace std;

const int MAX = 64; //圆盘的个数最多为64

struct st{  //用来表示每根柱子的信息
      int s[MAX]; //柱子上的圆盘存储情况
      int top; //栈顶，用来最上面的圆盘
      char name; //柱子的名字，可以是A，B，C中的一个
     
      int Top()//取栈顶元素
      {
            return s[top];
      }
      int Pop()//出栈
      {
            return s[top--];
      }
      void Push(int x)//入栈
      {
            s[++top] = x;
      }
} ;

long Pow(int x, int y); //计算x^y
void Creat(st ta[], int n); //给结构数组设置初值
void Hannuota(st ta[], long max); //移动汉诺塔的主要函数

int main(void)
{
      int n;
      cin >> n; //输入圆盘的个数
     
      st ta[3]; //三根柱子的信息用结构数组存储
      Creat(ta, n); //给结构数组设置初值

      long max = Pow(2, n) - 1;//动的次数应等于2^n - 1
      Hannuota(ta, max);//移动汉诺塔的主要函数

      system("pause");
      return 0;
}

void Creat(st ta[], int n)
{
      ta[0].name = 'A';
      ta[0].top = n-1;
      for (int i=0; i<n; i++) //把所有的圆盘按从大到小的顺序放在柱子A上
            ta[0].s[i] = n - i;
           
      ta[1].top = ta[2].top = 0;//柱子B，C上开始没有没有圆盘
      for (int i=0; i<n; i++)
            ta[1].s[i] = ta[2].s[i] = 0;
           
      if (n%2 == 0) //若n为偶数，按顺时针方向依次摆放 A B C
      {
            ta[1].name = 'B';
            ta[2].name = 'C';
      }
      else  //若n为奇数，按顺时针方向依次摆放 A C B
      {
            ta[1].name = 'C';
            ta[2].name = 'B';
      }
}

long Pow(int x, int y)
{
      long sum = 1;
      for (int i=0; i<y; i++)
            sum *= x;

      return sum;
}

void Hannuota(st ta[], long max)
{
      int k = 0; //累计移动的次数
      int i = 0;
      int ch;
      while (k < max)
      {
            //按顺时针方向把圆盘1从现在的柱子移动到下一根柱子
            ch = ta[i%3].Pop();
            ta[(i+1)%3].Push(ch);
            cout << ++k << ": " << "Move disk " << ch << " from " << ta[i%3].name << " to " << ta[(i+1)%3].name << endl;
            i++;
            //把另外两根柱子上可以移动的圆盘移动到新的柱子上
            if (k < max)
            {     //把非空柱子上的圆盘移动到空柱子上，当两根柱子都为空时，移动较小的圆盘
                  if (ta[(i+1)%3].Top() == 0 || ta[(i-1)%3].Top() > 0 && ta[(i+1)%3].Top() > ta[(i-1)%3].Top())
                  {
                        ch =  ta[(i-1)%3].Pop();
                        ta[(i+1)%3].Push(ch);
                        cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i-1)%3].name << " to " << ta[(i+1)%3].name << endl;
                  }
                  else
                  {
                        ch =  ta[(i+1)%3].Pop();
                        ta[(i-1)%3].Push(ch);
                        cout << ++k << ": " << "Move disk " << ch << " from " << ta[(i+1)%3].name << " to " << ta[(i-1)%3].name << endl;
                  }
            }
      }
}

 

也许二杈树是很好用的，在插入和查找的时候时间复杂度一般为O（logN），但如果左右子树失去平衡，也可能达到O（N）。为了防止这种现象发生，一种解决办法是是左右子树尽量保持平衡，即建立一种平衡有序树AVL树。     
    一棵AVL树是其每个结点的左子树和右子树的高度最多相差1的二杈有序树。空树的高度定义为-1。
    AVL树的结点声明；
typedef struct avlnode
{
    int height;//比普通二杈有序树多了一个高度信息 
    ElemType data;
    struct bnode *lchild, *rchild;
} *AvlTree, *Position;    
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
static int Height(Position P);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);

//----------AVL树基本操作的算法实现--------------------
递归算法： 
Position FindMin(AvlTree T)
{
    if(T==NULL)
        return NULL;
    else if(T->lchild == NULL)
        return T;
    else
        return FindMin(T->lchild);
}

Position FindMax(AvlTree T)
{
    if(T==NULL)
        return NULL;
    else if(T->rchild == NULL)
        return T;
    else
        return FindMax(T->rchild);
}
非递归算法：
Position FindMin(AvlTree T)
{
    if(T!=NULL)
    {
        while(T->lchild != NULL)
            T = T->lchild;
    }
    
    return T;
}

Position FindMax(AvlTree T)
{
    if(T!=NULL)
    {
        while(T->rchild != NULL)
            T = T->rchild;
    }
    
    return T;
}
//返回P点的高度 
static int Height(Position P)
{
    if(P==NULL)
        return -1;
    else
        return P->height;
}
//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，
这里用到了“单旋转”或“双旋转”的算法，分别适用于：
单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入 
单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入  
双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入 
双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入  
static Position SingleRotateWithLeft(Position K2)
{
    Position K1;
    
    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转 
    K2->lchild = K1->rchild;
    K1->rchild = K2;
    
    K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    
    return K1;
}

static Position SingleRotateWithRight(Position K2)
{
    Position K1;
    
    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转 
    K2->rchild = K1->lchild;
    K1->lchild = K2;
    
    K2->height = Max(Height(K2->lchild), Height(K2->rchild)) + 1;
    K1->height = Max(Height(K1->lchild), Height(K1->rchild)) + 1;
    
    return K1;
}

static Position DoubleRotateWithLeft(Position K3)
{
    K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转 
    
    return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转 
}

static Position DoubleRotateWithRight(Position K3)
{
    K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转 
    
    return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转 
}

//向AVL树插入结点的操作 
AvlTree Insert(float x, AvlTree T)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong"); 
            exit(1);
        }
        T->data = x;  
        T->height = 0;
        T->lchild = T->rchild = NULL;
    }
    else if(T->data == x)//不做任何插入操作 
        ;
    else if(T->data > x)//把s所指结点插入到左子树中
    {
          T->lchild = Insert(x, T->lchild);
          if(Height(T->lchild) - Height(T->rchild) == 2) //若平衡被破坏
          {
            if(x < T->lchild->data)     //若x比T的左孩子小，对T单左旋转  
                T = SingleRotateWithLeft(T);
            else                         //否则，对T双左旋转   
                T = DoubleRotateWithLeft(T);
        }
    }
    else      //把s所指结点插入到右子树中
    {
          T->rchild = Insert(x, T->rchild);
          if(Height(T->rchild) - Height(T->lchild) == 2)
          {
            if(x > T->rchild->data)    //若x比T的右孩子大，对T单右旋转  
                T = SingleRotateWithRight(T);
            else                        //否则，对T双右旋转   
                T = DoubleRotateWithRight(T);
        }
    }
    T->height = Max(Height(T->lchild), Height(T->rchild)) + 1;
    
    return T;   
}
int Max(int a, int b)
{
    if(a > b)
        return a;
    else
        return b;
}
还有一种AVL树，它的结构中不包含高度特征，但包含一个平衡因子bf，用来判断结点的平衡性，若左孩子比右孩子高，则bf==1；否则，bf==-1；若左右相等则bf==0。
    AVL树的结点声明；
enum  BALANCE{LH = 1, EH = 0, RH = -1};
typedef struct avlnode
{
    BALANCE bf;//比普通二杈有序树多了一个平衡因子信息
    ElemType data;
    struct avlnode *lchild, *rchild;
} *AvlTree, *Position;
//----------AVL树基本操作------------ ------------------------------
AvlTree MakeEmpty(AvlTree T);
Position Find(ElemType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElemType x, AvlTree T);
AvlTree Delete(ElemType x, AvlTree T);
ElemType Retrieve(Position P);

//----------AVL树基本操作的算法实现--------------------

//在对一棵AVL树进行插入操作后，可能会破坏它的平衡条件，因此必须对新的AVL树进行调整，
这里用到了“单旋转”或“双旋转”的算法，分别适用于：
单左旋转（SingleRotateWithLeft）；对结点p的左孩子的左子树进行一次插入
单右旋转（SingleRotateWithRight）；对结点p的右孩子的右子树进行一次插入
双左旋转（DoubleRotateWithLeft）；对结点p的左孩子的右子树进行一次插入
双右旋转（DoubleRotateWithRight）；对结点p的右孩子的左子树进行一次插入
Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
    K2->lchild = K1->rchild;
    K1->rchild = K2;

    return K1;
}

Position SingleRotateWithRight(Position K2)
{
    Position K1;

    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
    K2->rchild = K1->lchild;
    K1->lchild = K2;

    return K1;
}

Position DoubleRotateWithLeft(Position K3)
{
    K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转

    return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}

Position DoubleRotateWithRight(Position K3)
{
    K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转

    return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}

AvlTree LeftBalance(AvlTree T) //左平衡处理
{
      AvlTree lT = T->lchild;
      switch (lT->bf) //检查左树的平衡度，并做相应处理
      {
            case LH :   T = SingleRotateWithLeft(T); //若新结点插入在T的左孩子的左子树上，对T单左旋转
                        T->bf = lT->bf = EH;   //重新设置平衡度
                        break;
            case RH :   AvlTree rT = lT->rchild;//若新结点插入在T的左孩子的右子树上，对T双左旋转，并重新设置平衡度
                        switch (rT->bf)
                        {
                              case LH :   T->bf = RH;
                                          lT->bf = EH;
                                          break;
                              case EH :   T->bf = lT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = EH;
                                          lT->bf = LH;
                                          break
                        }
                        rT->bf = EH;
                        T = DoubleRotateWithLeft(T);
                        break;
      }
      return T;
}

AvlTree RightBalance(AvlTree T) //右平衡处理
{
      AvlTree rT = T->rchild;
      switch (rT->bf) //检查右树的平衡度，并做相应处理
      {
            case LH :   T = SingleRotateWithRight(T); //若新结点插入在T的右孩子的右子树上，对T单右旋转
                        T->bf = rT->bf = EH;   //重新设置平衡度
                        break;
            case RH :   AvlTree lT = rT->lchild;//若新结点插入在T的右孩子的左子树上，对T双右旋转，并重新设置平衡度
                        switch (lT->bf)
                        {
                              case LH :   T->bf = EH;
                                          rT->bf = RH;
                                          break;
                              case EH :   T->bf = rT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = LH;
                                          rT->bf = EH;
                                          break
                        }
                        lT->bf = EH;
                        T = DoubleRotateWithRight(T);
                        break;
      }
      return T;
}

//向AVL树插入结点的操作
AvlTree Insert(ElemType x, AvlTree T, bool & taller)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong");
            exit(1);
        }
        T->data = x;
        T->lchild = T->rchild = NULL;
        T->bf = EH;
        taller = true; //插入新结点，树“长高”，置taller为真值
    }
    else if(T->data == x)//不做任何插入操作
        taller = false; //树未长高，置taller为假值
    else if(T->data > x)//把x插入到左子树中
    {
          T->lchild = Insert(x, T->lchild, taller);
          if (taller)//已经插入左子树，且树“长高”，需要检查平衡度，并做相应处理
          {
                  switch(T->bf)
                  {
                        case LH :   T = LeftBalance(T);//原本左树高于右树，需做左平衡处理，树高不变
                                    taller = false;
                                    break;
                        case EH :   T->bf = LH;//原本左右等高，现在左高于右，且树“长高”
                                    taller = true;
                                    break;
                        case RH :   T->bf = EH; //原本右树高于左树，现在左右等高，树高不变
                                    taller = false;
                                    break;
                  }
            }
    }
    else      //把x插入到右子树中，仿照处理左树的方法处理
    {
            T->rchild = Insert(x, T->rchild, taller);
          if (taller)
          {
                  switch(T->bf)
                  {
                        case LH :   T->bf = EH;
                                    taller = false;
                                    break;
                        case EH :   T->bf = RH;
                                    taller = true;
                                    break;
                        case RH :   T = RightBalance(T);
                                    taller = false;
                                    break;
                  }
            }
    }

    return T;
}
AVL树应用示例:
 /*输入一组数,存储到AVL树中,并进行输出*/
#include <iostream>
using namespace std;

#define MAX 100
enum  BALANCE{LH = 1, EH = 0, RH = -1};
typedef struct avlnode
{
    BALANCE bf;//比普通二杈有序树多了一个平衡因子信息
    int data;
    struct avlnode *lchild, *rchild;
} *AvlTree, *Position;

int Input(int a[]);//输入数据到数组,未排序
void Print(const int a[], int len); //输入未排序的原始数据
AvlTree Sort(AvlTree A, const int a[], int len); //对数据进行排序
AvlTree Insert(int x, AvlTree T, bool & taller); //把数据存储到AVL树中
Position SingleRotateWithLeft(Position K2); //单左旋转
Position SingleRotateWithRight(Position K2); //单右旋转
Position DoubleRotateWithLeft(Position K3);//双左旋转
Position DoubleRotateWithRight(Position K3);//双右旋转
AvlTree LeftBalance(AvlTree T);// 左平衡处理
AvlTree RightBalance(AvlTree T); //右平衡处理
void inorder(const AvlTree bt); //中序遍历AVL树
void PrintBT(AvlTree bt); //输出二杈树

int main(void)
{
    int a[MAX]={0};
    int len;
    AvlTree A=NULL;

    len = Input(a);
    Print(a, len);
    printf("\n");
    A = Sort(A, a, len);
    PrintBT(A);
    printf("\n");
    inorder(A);
    system("pause");
      return 0;
}
int Input(int a[])
{
    int i=0;

    do{
        a[i++] = rand()%1000;//输入随机数
    } while(i<MAX);
    return i;
}
void Print(const int a[], int len)
{
    int i;

    for(i=0; i<len; i++)
        printf("%d\t", a[i]);
}
AvlTree Sort(AvlTree A, const int a[], int len)
{
    int i;
    bool taller = false;

    for(i=0; i<len; i++)
         A = Insert(a[i], A, taller);
    return A;
}
void inorder(const AvlTree bt)
{
    AvlTree p=bt, stack[MAX];//p表示当前结点，栈stack[]用来存储结点
    int top=-1;

    do
    {
        while(p != NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
        {
            stack[++top] = p;
            p = p->lchild;
        }
        if(top >= 0) //所有左孩子处理完毕后
        {
            p = stack[top--];//栈顶元素出栈
            printf("%d\t", p->data); //输出该结点
            p = p->rchild; //处理其右孩子结点
        }
    } while((p != NULL)||(top >= 0));
}

//向AVL树插入结点的操作
AvlTree Insert(int x, AvlTree T, bool & taller)
{
    if(T == NULL)
    {
        T = (Position)malloc(sizeof(struct avlnode));
        if(T == NULL)
        {
            puts("wrong");
            exit(1);
        }
        T->data = x;
        T->lchild = T->rchild = NULL;
        T->bf = EH;
        taller = true; //插入新结点，树“长高”，置taller为真值
    }
    else if(T->data == x)//不做任何插入操作
        taller = false; //树未长高，置taller为假值
    else if(T->data > x)//把x插入到左子树中
    {
          T->lchild = Insert(x, T->lchild, taller);
          if (taller)//已经插入左子树，且树“长高”，需要检查平衡度，并做相应处理
          {
                  switch(T->bf)
                  {
                        case LH :   T = LeftBalance(T);//原本左树高于右树，需做左平衡处理，树高不变
                                    taller = false;
                                    break;
                        case EH :   T->bf = LH;//原本左右等高，现在左高于右，且树“长高”
                                    taller = true;
                                    break;
                        case RH :   T->bf = EH; //原本右树高于左树，现在左右等高，树高不变
                                    taller = false;
                                    break;
                  }
            }
    }
    else      //把x插入到右子树中，仿照处理左树的方法处理
    {
            T->rchild = Insert(x, T->rchild, taller);
          if (taller)
          {
                  switch(T->bf)
                  {
                        case LH :   T->bf = EH;
                                    taller = false;
                                    break;
                        case EH :   T->bf = RH;
                                    taller = true;
                                    break;
                        case RH :   T = RightBalance(T);
                                    taller = false;
                                    break;
                  }
            }
    }

    return T;
}

Position SingleRotateWithLeft(Position K2)
{
    Position K1;

    K1 = K2->lchild;  //在K2和K1之间进行一次单左旋转
    K2->lchild = K1->rchild;
    K1->rchild = K2;

    return K1;
}

Position SingleRotateWithRight(Position K2)
{
    Position K1;

    K1 = K2->rchild;    //在K2和K1之间进行一次单右旋转
    K2->rchild = K1->lchild;
    K1->lchild = K2;

    return K1;
}

Position DoubleRotateWithLeft(Position K3)
{
    K3->lchild = SingleRotateWithRight(K3->lchild); //在K2和K1之间进行一次单右旋转

    return SingleRotateWithLeft(K3); //在K3和K2之间进行一次单左旋转
}

Position DoubleRotateWithRight(Position K3)
{
    K3->rchild = SingleRotateWithLeft(K3->rchild); //在K2和K1之间进行一次单左旋转

    return SingleRotateWithRight(K3);//在K3和K2之间进行一次单右旋转
}

AvlTree LeftBalance(AvlTree T) //左平衡处理
{
      AvlTree lT = T->lchild;
      switch (lT->bf) //检查左树的平衡度，并做相应处理
      {
            case LH :   T = SingleRotateWithLeft(T); //若新结点插入在T的左孩子的左子树上，对T单左旋转
                        T->bf = lT->bf = EH;   //重新设置平衡度
                        break;
            case RH :   AvlTree rT = lT->rchild;//若新结点插入在T的左孩子的右子树上，对T双左旋转，并重新设置平衡度
                        switch (rT->bf)
                        {
                              case LH :   T->bf = RH;
                                          lT->bf = EH;
                                          break;
                              case EH :   T->bf = lT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = EH;
                                          lT->bf = LH;
                                          break;
                        }
                        rT->bf = EH;
                        T = DoubleRotateWithLeft(T);
                        break;
      }
      return T;
}

AvlTree RightBalance(AvlTree T) //右平衡处理
{
      AvlTree rT = T->rchild;
      switch (rT->bf) //检查右树的平衡度，并做相应处理
      {
            case RH :   T = SingleRotateWithRight(T); //若新结点插入在T的右孩子的右子树上，对T单右旋转
                        T->bf = rT->bf = EH;   //重新设置平衡度
                        break;
            case LH :   AvlTree lT = rT->lchild;//若新结点插入在T的右孩子的左子树上，对T双右旋转，并重新设置平衡度
                        switch (lT->bf)
                        {
                              case LH :   T->bf = EH;
                                          rT->bf = RH;
                                          break;
                              case EH :   T->bf = rT->bf = EH; //我感觉这种情况应该不会出现
                                          break;
                              case RH :   T->bf = LH;
                                          rT->bf = EH;
                                          break;
                        }
                        lT->bf = EH;
                        T = DoubleRotateWithRight(T);
                        break;
      }
      return T;
}

void PrintBT(AvlTree bt)
{
    if(bt != NULL)
    {
        printf("%d", bt->data);
        if(bt->lchild!=NULL || bt->rchild!=NULL)
        {
            printf("(");
            PrintBT(bt->lchild);
            if(bt->rchild!=NULL)
                printf(",");
            PrintBT(bt->rchild);
            printf(")");
        }
    }
}

对于一般的二叉树来说，删去树中的一个结点是没有意义的，因为它将使以被删除的结点为根的子树变成森林，破坏了整棵树的结构
但是，对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点后不改变二叉排序树的特性即可。
      在二叉排序树上删除一个结点的算法如下：
btree * DeleteBST(btree *b, ElemType x)
{
      if (b)
      {
            if (b->data == x)
                  b = DelNode(b);
            else if (b->data > x)
                  b->lchild = DeleteBST(b->lchild, x);
            else
                  b->rchild = DeleteBST(b->rchild, x);
      }
      return b;
}
其中删除过程有两种方法。
第一种过程如下：
1。若p有左子树，找到其左子树的最右边的叶子结点r，用该叶子结点r来替代p，把r的左孩子
作为r的父亲的右孩子。
2。若p没有左子树，直接用p的右孩子取代它。

第二种过程如下：
1。若p有左子树，用p的左孩子取代它；找到其左子树的最右边的叶子结点r，把p的右子树作为r
的右子树。
2。若p没有左子树，直接用p的右孩子取代它。
    两种方法各有优劣，第一种操作简单一点点，但均衡性不如第二种，因为它将结点p的右子树
全部移到左边来了。下面将分别以两种种思路编写代码。


第一种：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子树;
        while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r
        {
            r = r->rchild;
        }
            r->rchild = p->rchild;

            btree *q = p->lchild;   //q指向其左子树;
            free(p);
            return q;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子树;
            free(p);
            return q;
      }
}

第二种：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子树;
            btree *prer = p->lchild;   //prer指向其左子树;
        while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r
        {
                  prer = r;
            r = r->rchild;
        }

        if(prer != r)//若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子
        {
                  prer->rchild = r->lchild;
                  r->lchild = p->lchild; //被删结点p的左子树作为r的左子树
            }
        r->rchild = p->rchild; //被删结点p的右子树作为r的右子树

            free(p);
            return r;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子树;
            free(p);
            return q;
      }
}
    但是上面这种方法，把r移来移去，很容易出错，其实在这里我们删除的只是p的元素值，而不是它的地址，所以完全没有必要移动指针。仔细观察，发现我们删除的地址实际上是p的左子树的最右边的叶子结点r的地址，所以我们只要把r的数据填到p中，然后把r删除即可。
算法如下：
btree * DelNode(btree *p)
{
      if (p->lchild)
      {
            btree *r = p->lchild;   //r指向其左子树;
            btree *prer = p->lchild;   //prer指向其左子树;
        while(r->rchild != NULL)//搜索左子树的最右边的叶子结点r
        {
                  prer = r;
            r = r->rchild;
        }
            p->data = r->data;

        if(prer != r)//若r不是p的左孩子，把r的左孩子作为r的父亲的右孩子
                  prer->rchild = r->lchild;
            else
            p->lchild = r->lchild; //否则结点p的左子树指向r的左子树

            free(r);
            return p;
      }
      else
      {
            btree *q = p->rchild;   //q指向其右子树;
            free(p);
            return q;
      }
}

二、任给 1<=n<=20 个不同的非零正整数，每个正整数最多使用1次，请问这n个正整数能够加和的结果共有多少种(不考虑和超出long的最大值的可以),
程序中请实现如下函数。用于计算数组data,中ncount的加和的数量。
long getsumcount(long data[], long count);
程序中可以出现别的辅助函数。或辅助结构等。

例如，
data[] = {1,2,3,4};
ncount = 4;
函数返回 10

分解如下。（0不算）

1  = 1
2  = 2
3  = 3 = 1+2
4  = 4 = 1+3

5  = 2+3 = 1+4
6  = 2+4 = 1+2+3
7  = 3+4 = 1+2+4
8  = 1+3+4
9  = 2+3+4
10 = 1+2+3+4
如上。所以结果是10种可能。
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <time.h>
#define libsize (1<<16)
#define hashsize (1<<16)
#define hashmask (0xffff)

using namespace std;

typedef struct node{
    long data;
    struct node *next;
}NODE;
NODE hashtab[hashsize];

const long MAX = 20;

bool IsNew(long array[], long len, long data);
void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num);
long _getsumcount(const long data[], long count);
long Sum(const long a[], int len);
long getsumcount(const long data[], long count);

int main(void)
{
      time_t startTime;
 time_t endTime;
 time(&startTime);
      long data[MAX]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

      for (long i=0; i<MAX; i++) //给数组赋值为1-100的随机数
      {
            long temp = rand()%100 + 1;
            if (IsNew(data, i, temp))
                  data[i] = temp;
      }

      for (long i=0; i<MAX; i++)
            cout << data[i] << ' ';
      cout << endl;

      int sum = 0;
      for (long i=1; i<=MAX; i++)
      {
            long s1 = getsumcount(data, i);
            long s2 = _getsumcount(data, i);
           
            cout << i << ": s1=" << s1 <<"  s2=" << s2 << endl;
            if (s1 == s2)
                  sum++;
      }
      cout << sum << endl;

      time(&endTime);
 cout << "time:" << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}
//////////////////////////////////////////////////////////////////////////
/*
  Author: goal00001111
*/
bool IsNew(long array[], long len, long data)
{
      for(int i=0; i<=len; i++)
            if (array[i] == data)
                  return false;
      return true;
}

long _getsumcount(const long data[], long count)
{
      bool lib[libsize];
      for (long i=0; i<libsize; i++)
            lib[i] = false;
      long *a = new long[count];

      for (int k=0; k<count; k++)
            solve(data, lib, a, count, 0, k, 0);

      delete []a;
      long sum = 1;
      for (long i=0; i<libsize; i++)
      {
            if (lib[i])
            {
                  sum++;
                // cout << i << ' ';
            }
      }
      return sum;
}

void solve(const long data[], bool lib[], long a[], long len, long pos, long max, long num)
{
      if (num == max)
      {
            for (int i=pos; i<len; i++)
            {
                  a[num] = data[i];
                  lib[Sum(a, num)] = true;
            }
      }
      else  //如果不是最后一个数字
      {
            for (int i=pos; i<len; i++)
            {
                  a[num] = data[i];
   solve(data, lib, a, len, i+1, max, num+1); //分析下一个数
            }
      }
}

long Sum(const long a[], int len)
{
      long sum = 0;
      for (int i=0; i<=len; i++)
            sum += a[i];
      return sum;
}
///////////////////////////////////////////////////////////////////////
/*
  Author: eastcowboy
*/

/*寻找并插入，找到而未插入返回0，未找到而插入返回1*/
static int hashinsert(long sum)
{
    NODE *p,*q;
    p = hashtab+ (sum & hashmask);
    while( p && (p->data!=sum) )
    {   q = p;
        p = p->next;
    }
    if( p )
        return 0;
    q->next = p = (NODE*)malloc(sizeof(NODE));
    p ->next = NULL;
    p ->data = sum;
    return 1;
}
/*删除hash表的第index条目*/
static void hashdelete(long index)
{   NODE *p,*q;
    p = hashtab[index].next;
    while(p)
    {   q = p;
        p = p->next;
        free(q);
    }
}
/*这才是正主^^*/
long getsumcount(const long data[],long count)
{
    long i;
    int state[MAX] = {0};
    long sum = 0,sp = 0;
    int ret = 1; /*由于0已经先放入表中，所以首先就有一个*/

    /*hash表初始化*/
    for(i=0;i<hashsize;++i)
    {   hashtab[i].data = 0;
        hashtab[i].next = NULL;
    }
    /*回溯求解*/
    while(sp>=0)
    {   if(sp==count)
        {   ret += hashinsert(sum);
            --sp;
        }
        switch( state[sp] )
        {   case 0:
                state[sp] = 1;
                sum += data[sp];
                ++sp;
                break;
            case 1:
                state[sp] = 2;
                sum -= data[sp];
                ++sp;
                break;
            case 2:
                state[sp] = 0;
                --sp;
                break;
        }
    }
    /*hash表销毁*/
    for(i=0;i<hashsize;++i)
    {   hashdelete(i);
    }
    return ret;
}

/*
  Name:6.剪刀石头布
  Copyright:
  Author:
  Date: 28-05-06 08:51
  Description:
N个小孩正在和你玩一种剪刀石头布游戏（剪刀赢布，布赢石头，石头赢剪刀）。N个小孩中有一个是裁判，其余小孩分成三组（不排除某些组没有任何成员的可能性），但是你不知道谁是裁判，也不知道小孩们的分组情况。然后，小孩们开始玩剪刀石头布游戏，一共玩M次，每次任意选择两个小孩进行一轮，你会被告知结果，即两个小孩的胜负情况，然而你不会得知小孩具体出的是剪刀、石头还是布。已知各组的小孩分别只会出一种手势（因而同一组的两个小孩总会是和局），而裁判则每次都会随便选择出一种手势，因此没有人会知道裁判到底会出什么。请你在M次剪刀石头布游戏结束后，猜猜谁是裁判。如果你能猜出谁是裁判，请说明最早在第几次游戏结束后你就能够确定谁是裁判。

输入要求：
输入文件包含多组测试数据，每组测试数据第一行为两个整数N和M(1<=N<=500，0<M<=2000)，分别为小孩的个数和剪刀石头布游戏进行的次数。接下来M行，每行两个整数且中间以一个符号隔开。两个整数分别为进行游戏的两个小孩各自的编号（为小于N的非负整数）。符号的可能值为“=”、“>”和“<”，分别表示和局、第一个小孩胜和第二个小孩胜三种情况。例：
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0

 

输出要求：
1．每组测试数据输出一行，若能猜出谁是裁判，则输出裁判的编号，并输出在第几次游戏结束后就能够确定谁是裁判，小孩的编号和游戏次数以一个空格隔开；
2．如果无法确定谁是裁判，输出-2；如果发现剪刀石头布游戏的胜负情况不合理（即无论谁是裁判都会出现矛盾），则输出-1。例：
-2
1 4
-1
0 0

 

评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有5个测试用例，每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为5%、10%、15%、30%和40%；
4．该题目20分。
*/

/*
算法介绍：
1。如果只有1个人，参加比赛，那么他就是裁判，即输出：0 0 。
2。建立数组 players[MAX][MAX] 记录比赛结果（数组赋初值0），若选手a输给b，则players[a][b]=1，players[b][a]=3；若打平，则players[a][b]=players[b][a]=2；
注意：在记录成绩之前，先判断选手a，b 是否已经比赛过，如果已经比赛过，则判断先前的比赛结果是否与当前结果相同，若不相同，在数组judger[]中做标记（数组赋初值0），若judger[a]=0，使judger[a]=1，表示a有可能为裁判；若judger[a]=1，则使judger[a]=2，表示a肯定为裁判，因为他和两个人出现不同结果。
同理处理b。
3。遍历数组judger[]，用temp1记录judger[i]=1出现的次数，用temp2记录judger[i]=2出现的次数，如果2个或以下的人可能为裁判，且没有人肯定为裁判，即if (temp1 <= 2 && temp2 == 0)，则无法确定谁是裁判；
如果2个或以下的人可能为裁判，且有1人肯定为裁判，即if (temp1 <= 2 && temp2 == 1)，则确定裁判i；
如果2个以上的人可能为裁判，即if (temp1 > 2)，则胜负情况不合理。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 500;
void Readata(const char *filename);

int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

 Readata("in.txt");

 time(&endTime);
 cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void Readata(const char *filename)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            int N, M;
            in >> N;
            in >> M;
           
            if (N == 1) //如果只有1个人，参加比赛，那么他就是裁判
                  cout << 0 << ' ' << 0 << endl;
                 
            int players[MAX][MAX] = {0};//记录比赛结果
            int *judger = new int[N];//记录是否可能为裁判，0表示不可能，1表示可能，2表示确定
            for (int i=0; i<N; i++)
                  judger[i] = 0;
                 
            int n = 0;//累计比赛场数
            int min = n;//存储能够确定谁是裁判的最少场数
            while (!in.eof() && n < M)//读入比赛结果信息
            {
                  char data[3]; //存储比赛选手编号和结果

                  in >> data[0];
                  in >> data[1];
                  in >> data[2];
                 // cout << data[0] << ' ' << data[1] << ' ' << data[2] << endl;
                  n++;
                  int flag = (data[1]=='<')? 1 :((data[1]=='=')? 2 : 3);//分别用1，2，3表示负，平，胜
                 
                  if (players[data[0]-'0'][data[2]-'0'] == 0)//若a,b未对局过，存储比赛结果
                  {
                        players[data[0]-'0'][data[2]-'0'] = flag;
                        players[data[2]-'0'][data[0]-'0'] = 4 - flag;
                  }
                  else if (players[data[0]-'0'][data[2]-'0'] != flag)//若a,b已对局过，且比赛结果不同
                  {
                        if (judger[data[0]-'0'] == 0) //a有可能为裁判
                              judger[data[0]-'0'] = 1;
                        else if (judger[data[0]-'0'] == 1)//a就是裁判
                        {
                              judger[data[0]-'0'] = 2;
                              min = n;
                        }
                       
                        if (judger[data[2]-'0'] == 0) //b有可能为裁判
                              judger[data[2]-'0'] = 1;
                        else if (judger[data[2]-'0'] == 1) //a就b是裁判
                        {
                              judger[data[2]-'0'] = 2;
                              min = n;
                        }
                  }
                 // cout << "players["<<data[0]-'0'<<"]["<<data[2]-'0'<<"]="<<players[data[0]-'0'][data[2]-'0']<<endl;
            }
            int temp1 = 0; //记录judger[i]=1出现的次数
            int temp2 = 0; //记录judger[i]=2出现的次数
            int answer;
            for (int i=0; i<N; i++)
            {
                  //cout << judger[i] << ' ';
                  if (judger[i] == 1)
                       temp1++;

                  if (judger[i] == 2)
                  {
                       temp2++;
                       answer = i;
                  }
            }
            cout << endl;
            if (temp1 <= 2 && temp2 == 0)
                  cout << -2 << endl;
            else  if (temp1 <= 2 && temp2 == 1)
                  cout << answer << ' ' << min << endl;
            else  if (temp1 > 2)
                  cout << -1 << endl;
                 
            delete []judger;
      }

    in.close(); //关闭文件
}

 

/*
  Name:
  Copyright:
  Author:
  Date: 28-05-06 15:26
  Description: 5.座位调整
百度办公区里到处摆放着各种各样的零食。百度人力资源部的调研发现，员工如果可以在自己喜欢的美食旁边工作，效率会大大提高。因此，百度决定进行一次员工座位的大调整。

调整的方法如下：
1．首先将办公区按照各种零食的摆放分成N个不同的区域（例如：可乐区，饼干区，牛奶区等等）；
2．每个员工对不同的零食区域有不同的喜好程度（喜好程度是1~100的整数， 喜好程度越大表示该员工越希望被调整到相应的零食区域）；
3．由于每个零食区域可以容纳的员工数量有限，人力资源部希望找到一个最优的调整方案使得总的喜好程度最大。

输入要求：
文件第一行包含两个整数N，M(N>=1，M<=300)。分别表示N个区域和M个员工；
第二行是N个整数构成的数列a，其中a[i]表示第i个区域可以容纳的员工数(1<=a[i]<=M，a[1]+a[2]+...+a[N]=M)；
紧接着是一个M*N的矩阵P，P(i,j)表示第i个员工对第j个区域的喜好程度。例：
3 3
1 1 1
100 50 25
100 50 25
100 50 25

输出要求：
对于每个测试数据，输出可以达到的最大的喜好程度。例：
175

 

数据解释：
此数据只存在一种安排方法，三个员工分别安置在三个区域。最终的喜好程度为100+50+25=175

评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有4个测试用例，每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为25%，25%，25%，25%；
4．该题目20分。

*/
/*
算法介绍：
1。读入数据N，M，a[]和p[][]。
2。以员工为主序，采用回溯的方法依次处理每一个员工在每个位置的喜好程度，返回总的最大的喜好程度。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 301;
void Readata(const char *filename, int a[], int p[][MAX], int & N, int & M);
int GetPlace(int N, int maxMen, int man, const int p[][MAX], int a[]);

int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

      int N, M;
      int a[MAX] = {0};
      int p[MAX][MAX] = {0};

 Readata("in5.txt", a, p, N, M);//读入数据

// cout << M << ' ' << N << endl;
// for (int i=1; i<=N; i++)
//            cout << a[i] << ' ';
//      cout << endl;
//      for (int i=1; i<=M; i++)
//      {
//            for (int j=1; j<=N; j++)
//                  cout << p[i][j] << ' ';
//            cout << endl;
//      }

      int sum = GetPlace(N, M, 1, p, a);//返回总的最大的喜好程度。
      cout << sum << endl;

 time(&endTime);
 cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void Readata(const char *filename, int a[], int p[][MAX], int & N, int & M)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            in >> N;
            in >> M;
            for (int i=1; i<=N; i++)
                  in >> a[i];
            for (int i=1; i<=M; i++)
                  for (int j=1; j<=N; j++)
                        in >> p[i][j];
      }

    in.close(); //关闭文件
}

int GetPlace(int N, int maxMen, int man, const int p[][MAX], int a[])
{
      int max = 0;
      int sum = 0;

      if (man == maxMen)//处理最后一个员工
      {
            for (int i=1; i<=N; i++)
            {
                  if (a[i] > 0)//如果该位置还可以容纳此员工，用sum记录其在该处的喜好度
                        sum = p[man][i];
                  if (sum > max)
                        max = sum;//用max记录该员工可以获得的最大喜好度
            }
      }
      else //如果处理的不是最后一个员工，应采用回溯方法以取得最优解
      {
            for (int i=1; i<=N; i++)
            {
                  if (a[i] > 0)//如果该位置还可以容纳此员工，用sum记录其在该处的喜好度
                  {
                        a[i]--;//该位置可容纳员工数减1
                        sum = p[man][i] + GetPlace(N, maxMen, man+1, p, a);
                        a[i]++;
                  }
                  if (sum > max)
                        max = sum;
            }
      }
      return max; //返回第man到M个员工总的最大喜好度
}

 

/*3.变态比赛规则
为了促进各部门员工的交流，百度举办了一场全公司范围内的“拳皇”（百度内部最流行的格斗游戏）友谊赛，负责组织这场比赛的是百度的超级“拳皇”迷W.Z。W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相邻部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，
W.Z希望员工自由分组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人之间不会打任何比赛。

比如4个人，编号为1~4,如果分为两个组并且1，2一个组，3，4一个组，那么一共需要打四场比赛：
1 vs 3，1 vs 4，2 vs 3，2 vs 4。 而如果是1，2，3一组，4单独一组，那么一共需要打三场比赛:
      1 vs 4，2 vs 4，3 vs 4。

很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人，
通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，
如果分到两组则需要2场比赛，如果分为三组则需要3场比赛。但是无论怎么分都不可能恰需要1场比赛。

相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

输入要求：
每行为一组数据，包含两个数字 N, K(0<N<=500, K>=0)。例：
2 0
2 1
3 1
3 2

 

输出要求：
对输入的N,K 如果N个员工通过一定的分组方式可以使比赛场数恰好为K，则输出"YES"，否则输出"NO"
（请全部使用大写字母），每组数据占一行。例：
YES
YES
NO
YES

*/
/*
算法分析：采用递归的方法，原理较简单，大家看源码即可。
*/

/*
  Name:
  Copyright:
  Author:
  Date: 27-05-06 15:37
  Description:
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 100;
void Readata(const char *filename);
bool check(long n, long k);

int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

 Readata("in.txt");

 time(&endTime);
 cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void Readata(const char *filename)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      while (!in.eof())
      {
            long data[2];

            in >> data[0];
            in >> data[1];
            //cout << data[0] << ' ' << data[1] << endl;

            if (check(data[0], data[1]))
                  cout << "YES" << endl;
            else
                  cout << "NO" << endl;
      }

    in.close(); //关闭文件
}
bool check(long n, long k)
{
    bool flag = false;
    int i;
    if(k == 0) //可能  。。。1
        return true;
    if(n==0 && k || k<0)  //不可能 。。。2
        return false;
    for(i=1; i<n && !flag; i++) //i表示将被减掉的小组的人数，每少一个由i个人组成的组就会少(n-i) * i场比赛
        flag = check(n-i,k - (n-i) * i);  //不断的减少小组数和对应减少的比赛次数，直到出现1或2的情况 （出现可能的情况也会终止分析）
    return flag;
}

 /*
  Name:
  Copyright:
  Author:
  Date: 28-05-07 15:26
  Description: 2.饭团的烦恼
“午餐饭团”是百度内部参与人数最多的民间组织。
同一个部门的、同一所大学的、同一年出生的、使用同一种型号电脑的员工们总是以各种理由组织各种长期的、临时的饭团。

参加饭团，不仅可以以优惠的价格尝到更加丰富的菜式，还可以在吃饭的时候和同事们增进感情。
但是，随着百度的员工越来越多，各个饭团的管理变得繁杂起来。特别是为了照顾员工们越来越挑剔的胃，饭团的点菜负责人的压力也越来越大。现在，这个任务就交给“百度之星”了，因为，你将要为所有的百度饭团设计一个自动点菜的算法。

饭团点菜的需求如下：
1．经济是我们要考虑的一个因素，既要充分利用百度员工的午餐补助，又不能铺张浪费。因此，我们希望最后的人均费用越接近12元越好。
2．菜式丰富是我们要考虑的另一个因素。为简单起见，我们将各种菜肴的属性归结为荤菜，素菜，辛辣，清淡，并且每个菜只能点一次。
3．请谨记，百度饭团在各大餐馆享受8折优惠。

输入要求：
1．输入数据第一行包含三个整数N，M，K(0<N<=16，0<M<=N，0<K<=12)，分别表示菜单上菜的数目，饭团需要点的菜的数目，就餐的人数；
2．紧接着N行，每行的格式如下：
菜名（长度不超过20个字符） 价格（原价，整数） 是否荤菜（1表示是，0表示否） 是否辛辣（1表示是，0表示否）；
3．第N+2行是 a b c d 四个整数，分别表示需要点的荤菜，素菜，辛辣，清淡菜的数目。例：
3 2 2
水煮鱼 30 1 1
口水鸡 18 1 1
清炖豆腐 12 0 0
1 1 1 1

 

输出要求：
对于每组测试数据，输出数据包含M+1行，前M行每行包含一个菜名（按菜名在原菜单的顺序排序）。第M+1行是人均消费，结果保留两位小数。例：
口水鸡
清炖豆腐
12.00

评分规则：
1．程序将运行在一台Linux机器上（内存使用不作严格限制），在每一测试用例上运行不能超过10秒，否则该用例不得分；
2．要求程序能按照输入样例的格式读取数据文件，按照输出样例的格式将运行结果输出到标准输出上。如果不能正确读入数据和输出数据，该题将不得分；
3．该题目共有5个测试用例，每个测试用例为一个输入文件。各测试用例占该题目分数的比例分别为20%，20%，20%，20%，20%；
4．该题目10分。
*/
/*
算法介绍：
1。读入数据。
2。以菜的个数为主序，采用回溯的方法依次处理每个菜的可能性，返回最好的点菜方法:
      即将问题转化为：从N个不同的数中选出满足要求的M个数。
      解决办法为先从N个不同的数中选出M个数，再判断这M个数是否满足要求，满足要求则存储到数组bestdish[]，并根据当前实际最佳金额与理论最佳金额的差值，实时更换数组bestdish[]的值，最后得到的数组bestdish[]就是最佳数组bestdish[]。
3。根据数组bestdish[]，输出结果。
*/

#include <iostream>
#include<fstream>
#include <time.h>

using namespace std;

const int MAX = 21;
double Min = 1000000;//存储当前实际最佳金额与理论最佳金额的差值
double pay; //存储当前实际最佳金额
double bestPay; //存储所需的理论最佳金额，恰好每人12元
int N, M, K;
int hunCai;
int suCai;
int xinLa;
int qingDan;

class Dish{
public:
      char name[MAX];
      double price;
      bool isMeat;
      bool isAcridity;

      void PutData(const char *na, double p, bool m, bool acr) //输入数据
      {
            strcpy(name, na);
            price = p;
            isMeat = m;
            isAcridity = acr;
      }

      void PrintData()
      {
            cout << name << ' ' << price << ' ' << isMeat << ' ' << isAcridity << endl;
      }
};

void ReadData(const char *filename, Dish **obj);
double Abs(double a);
bool IsPass(const int pass[], const Dish *obj, double & sum);
void GetDishes(int num, int pos, const Dish *obj, int pass[], int bestDish[]);

int main()
{
 time_t startTime;
 time_t endTime;
 time(&startTime);

      Dish *obj;

 ReadData("in3.txt", &obj);//读入数据

 //cout << N << ' ' << M << ' ' << K << endl;
// for (int i=0; i<N; i++)
//            obj[i].PrintData();
//      cout << hunCai << ' ' << suCai << ' ' << xinLa << ' ' << qingDan << endl;

      bestPay = K * 12; //存储所需的理论最佳金额，恰好每人12元
      int *pass = new int[N+1]; //存储已经被点了的菜
      int *bestDish = new int[N+1]; //存储最佳被点了的菜

      GetDishes(1, 0, obj, pass, bestDish); //以菜的个数用回溯的方法求最佳点菜方案
     
      for (int i=1; i<=M; i++)
      {
            cout << obj[bestDish[i]].name << endl;
      }
      printf("%.2f\n", pay / K);
     
      delete []pass;
      delete []bestDish;
     
 time(&endTime);
// cout << difftime(endTime, startTime) << endl;

 getchar();
 return 0;
}

void GetDishes(int num, int pos, const Dish *obj, int pass[], int bestDish[])
{
      if (num == M)//处理最后一个菜
      {
            for (int i=pos; i<N; i++)
            {
                  pass[num] = i;
                  double sum = 0;
                  if (IsPass(pass, obj, sum) && Abs(sum-bestPay)<Min) //若该道菜满足口味要求，并最接近理论最佳金额
                  {
                        pay = sum;  //存储当前实际最佳金额
                        Min = Abs(sum-bestPay);//存储当前最小差别
                        for (int i=1; i<=M; i++)
                              bestDish[i] = pass[i];
                  }
            }
      }
      else //如果处理的不是最后一个菜，应采用回溯方法以取得最优解
      {
            for (int i=pos; i<N-M+num; i++)
            {
                 pass[num] = i;
                 GetDishes(num+1, i+1, obj, pass, bestDish);
            }
      }
}

bool IsPass(const int pass[], const Dish *obj, double & sum)
{
      int h = 0; //存储实际已经点了的荤菜
      int s = 0; //存储实际已经点了的素菜
      int x = 0; //存储实际已经点了的辛辣菜
      int q = 0; //存储实际已经点了的清淡菜
      for (int j=1; j<=M; j++)
      {
            sum += obj[pass[j]].price * 0.8;
            if (obj[pass[j]].isMeat && h < hunCai)//分析该道菜的各种属性
                  h++;
            else if (!obj[pass[j]].isMeat && s < suCai)
                  s++;
            else
                  return false;
            if (obj[pass[j]].isAcridity && x < xinLa)
                  x++;
            else if (!obj[pass[j]].isAcridity && q < qingDan)
                  q++;
            else
                  return false;
      }
      return true;
}

double Abs(double a)
{
      return (a > 0) ? a : -a;
}

void ReadData(const char *filename, Dish **obj)
{
      fstream in(filename);
      if (!in)
            return ;   //结束程序执行

      in >> N;
      in >> M;
      in >> K;

      *obj = new Dish[N];
      int n = 0;
      while (!in.eof() && n < N)
      {
            char name[MAX];
            double price;
            bool isMeat;
            bool isAcridity;

            in >> name;
            in >> price;
            in >> isMeat;
            in >> isAcridity;

            (*obj)[n++].PutData(name, price, isMeat, isAcridity);
      }
      in >> hunCai;
      in >> suCai;
      in >> xinLa;
      in >> qingDan;

      in.close(); //关闭文件
}