水壶(Kettle)问题

8-4  水壶

   假设给定了n个红色的水壶和n个蓝色的水壶，它们的形状和尺寸都不相同。所有红色水壶中所盛水的量都不一样，蓝色水壶也是一样。此外，对于每个红色的水壶，都有一个对应的蓝色水壶，两者所盛的水量是一样的。反之亦然。

  你的任务是将所盛水量一样的红色水壶和蓝色水壶找出来。为了达到这一目的，可以执行如下操作:挑选出一对水壶，其中一个是红色的，另一个是蓝色的：将红色水壶中倒满水；再将水倒入到蓝色的水壶中。通过这个操作，可以判断出来这两只水壶的容量哪一个大，或者是一样大。假设这样的比较需要一个时间单位。你的目标是找出一个算法，它通过执行最少次数的比较，来确定分组和配对问题。记住不能直接比较两个红色的或两个蓝色的水壶。

  a）给出一个确定型的算法，它利用Θ(n^2)次比较来完成水壶的配对。

  b）证明：对于一个可以解决本问题的算法，必须执行的比较次数的下界为Ω(nlgn)。

  c）给出一个随机化的算法，其期望的比较次数为O(nlgn)，并证明这个界是正确的。对你的算法来说，最坏情况下的比较次数是什么？

a)先用朴素的方法，拿出第1个红色水壶，然后从n个蓝色水壶中去配对，需要Θ(n)次比较。重复上述操作，知道所有的红色水壶都完成了配对。总的时间复杂度为Θ(n^2)

b)采用决策树的方法进行分析，总共可能的配对有n!种，每次比较的产生的分支有3个(大于、相等或小于)，若决策树的高度为h，则Ω(nlgn)就是比较次数的下界。

c) 由于每个红色的水壶和蓝色的水壶都有一个配对，因此理论上我们只需要分别将其进行排序即可。但是实际问题中，是不容许两个各红色或蓝色的水壶进行比较的，必须颜色不一样的水壶才能进行比较。因此需要一定的技巧。

     整个排序的过程中采用快速排序的思想，现对最关键也是有所不同的PATITION部分，这个过程有点类似交叉验证，具体描述如下：

1. 从红色水壶序列中随机选择一个作为枢轴元素

2. 在蓝色水壶序列中查找和该红色水壶容量一样的那个作为枢轴元素

3. 利用红色水壶枢轴元素对蓝色水壶序列进行PATITION。

4. 利用蓝色水壶枢轴元素对红色水壶序列进行PATITION。

如此PATIION部分就完成了，期望的时间复杂度为Θ(n)。整个过程类似快排迭代进行即可完成排序。

整个时间的复杂度为：即时间复杂度为O(nlgn)。最坏的情况下时间复杂度为O(n^2)。

下面是一个简单的代码实现:

struct Kettle
{
    int I,V;//水壶的初始下标，容量
    Kettle():I(0),V(0){}
    Kettle(int _i,int _v):I(_i),V(_v){}
};

/*随机产生[L,R]上的随机数*/
int Rand(int L,int H)
{
    return rand()%(H-L+1) + L;
}
istream& operator>>(istream& in,Kettle& k)
{
    in>>k.I>>k.V;
    return in;
}
void swap(Kettle& lh,Kettle& rh)//重载swap函数
{
    swap(lh.I,rh.I);
    swap(lh.V,rh.V);
}

/*
A代表红色水壶
B代表蓝色水壶
L,R表示当前处理的数据在数组中的上下界
step 1:从A中随机选择一个壶r
step 2:从蓝色水壶中找到和r容量一样的蓝色水壶b
step 3:将r作为蓝色水壶Partition的分隔元素，b作为红色水壶Partition的分隔元素
*/
int Partition(Kettle* A,Kettle *B,int L,int R)
{
    int I = Rand(L,R),J;
    int bKey = A[I].V;//从红色中随机选取的分隔元素,做蓝色的分隔元素

    for(J=L; J<=R; ++J)//找B中和rKey一样的元素
        if(B[J].V==bKey)
        {
            cout<<"A["<<A[I].I<<"] = B["<<B[J].I<<"] = "<<bKey<<endl;
            break;
        }
    int rKey = B[J].V; //做红色的分隔元素

    int j,ir=L-1;
    swap(A[I],A[R]);
    for(j=L; j<R; ++j)//对红色水壶进行划分
    {
        if(A[j].V<=rKey)
        {
            ++ir;
            swap(A[ir],A[j]);
        }
    }
    swap(A[ir+1],A[R]);

    int ib=L-1;
    swap(B[J],B[R]);
    for(j=L; j<R; ++j)//对蓝色水壶进行划分
    {
        if(B[j].V<=bKey)
        {
            ++ib;
            swap(B[ib],B[j]);
        }
    }
    swap(B[ib+1],B[R]);
    return ir+1;//这里肯定 ib==ir
}

void Match(Kettle *A,Kettle *B,int L,int R)//整个过程和快排基本一致
{
    if(L < R)
    {
        int M = Partition(A,B,L,R);
        Match(A,B,L,M-1);
        Match(A,B,M+1,R);
    }
    else if(L==R) //单个的元素直接配对
        cout<<"A["<<A[L].I<<"] = B["<<B[L].I<<"] = "<<A[L].V<<endl;
}

void TestPartition()
{
    srand(11);
    int a[] = {2, 3, 7, 5, 1, 9, 6, 8, 4};
    int b[] = {4, 7, 9, 5, 1, 3, 8, 2, 6};
    Kettle A[9],B[9];
    for(int i=0;i<9;++i)
    {
        A[i].I = i; A[i].V = a[i];
        B[i].I = i; B[i].V = b[i];
    }
    Match(A,B,0,8);
}