Uva 10132 - File Fragmentation

发表于 2012-03-30 分类于算法，算法题阅读次数： Valine：
本文字数： 4k 阅读时长 ≈ 4 分钟

这个题，粗看之下还没怎么看懂，这个应该跟我英语水平有关系。然后再看输入输出，渐渐的才明白什么意思。原来是要把2 * N张破纸组合成N张一样的纸。我历来思维比较随便，不是很严谨的那种。然后，想了一下发现一定会有大于等于N张破纸片是符合前半部分模式的。
那么，可以建一个字典树，把所有的是前半张纸的找出来。然后根据这前半张纸，找出剩下的后半张纸（因为知道一整张纸的长度，所以知道剩下的半张纸的长度）。但是写出来就发现这样不严谨，是不对的。因为单纯根据已经找出来的前半张纸，无法确定后半张纸（事实上，只能确定其长度而已）。
那么只能找其它方法了，再检查了下数据范围，发现比较小，那么意味着可以暴力求解了。好吧，那就深搜吧。我把所有的破纸片按照它们的长度分成一些集合，对于长度为len的纸片集合，只要与长度为nAnsLen - len的纸片集合进行搜索匹配，找出一个可行的解即可了。我又想当然的认为只要匹配一对集合即可了，那么很显然又是错的了。好吧，我只能对所有集合进行匹配了。对每一对集合进行深搜回溯来匹配待选的Ans，而这个Ans是从第一对集合中搜索出来的答案。
代码写得很冗长，很复杂，差不多200多行了。真的是水平有限，这种题很明显应该有更方便的解法的，而且我的代码应该不至于写得这么乱的。后面还是错了很多次，发现了很多bug，比如我如果搜索长度为nAnsLen/2的集合时就必须进行特殊处理。还有最后一个样例后面不能输出’\n’，而且uvaoj不能对这个换行判PE，一直是WA，实在是让人崩溃。

#include <stdio.h>
#include <string.h>
#define MAX (256 + 10)
#define MAX_NUM (150)

char szLines[MAX_NUM][MAX];
char szAns[MAX];

struct SET
{
    int nNum;
    char szLines[MAX_NUM][MAX];
    bool bUsed[MAX];
};

SET sets[MAX];
char szTmpOne[MAX];
char szTmpTwo[MAX];
int nAnsLen;
bool bFind;

void dfs(int nI, int nNum)
{
    if (nNum == 0)
    {
        bFind = true;
    }
    else
    {
        for (int i = 0; i < sets[nI].nNum && !bFind; ++i)
        {
            for (int j = 0; j < sets[nAnsLen - nI].nNum && !bFind; ++j)
            {
                if (nI == nAnsLen - nI && i == j)
                {
                    continue;
                }

                if (!sets[nI].bUsed[i] && !sets[nAnsLen - nI].bUsed[j])
                {
                    strcpy(szTmpOne, sets[nI].szLines[i]);
                    strcat(szTmpOne, sets[nAnsLen - nI].szLines[j]);
                    strcpy(szTmpTwo, sets[nAnsLen - nI].szLines[j]);
                    strcat(szTmpTwo, sets[nI].szLines[i]);

                    //printf("%s\n", szAns);
                    if (strcmp(szTmpOne, szAns) == 0 || strcmp(szTmpTwo, szAns) == 0)
                    {
                        sets[nI].bUsed[i] = sets[nAnsLen - nI].bUsed[j] = true;
                        if (!bFind)
                        {
                            if (nI == nAnsLen - nI)
                            {
                                dfs(nI, nNum - 2);
                            }
                            else
                            {
                                dfs(nI, nNum - 1);
                            }
                        }
                        sets[nI].bUsed[i] = sets[nAnsLen - nI].bUsed[j] = false;
                    }
                }
            }
        }
    }
}

bool Find(int nI)
{
    bFind = false;
    for (int i = 0; i < sets[nI].nNum && !bFind; ++i)
    {
        for (int j = 0; j < sets[nAnsLen - nI].nNum && !bFind; ++j)
        {
            if (nI == nAnsLen - nI && i == j)
            {
                continue;
            }

            sets[nI].bUsed[i] = true;
            sets[nAnsLen - nI].bUsed[j] = true;

            strcpy(szAns, sets[nI].szLines[i]);
            strcat(szAns, sets[nAnsLen - nI].szLines[j]);
            if (nI == nAnsLen - nI)
            {
                dfs(nI, sets[nI].nNum - 2);
            }
            else
            {
                dfs(nI, sets[nI].nNum - 1);
            }
            if (bFind)
            {
                for (int k = nI + 1; k <= nAnsLen / 2; ++k)
                {
                    bFind = false;
                    dfs(k, sets[k].nNum);
                    if (!bFind)
                    {
                        break;
                    }
                }
                if (bFind)
                {
                    return true;
                }
            }

            strcpy(szAns, sets[nAnsLen - nI].szLines[j]);
            strcat(szAns, sets[nI].szLines[i]);
            if (nI == nAnsLen - nI)
            {
                dfs(nI, sets[nI].nNum - 2);
            }
            else
            {
                dfs(nI, sets[nI].nNum - 1);
            }
            if (bFind)
            {
                for (int k = nI + 1; k <= nAnsLen / 2; ++k)
                {
                    bFind = false;
                    dfs(k, sets[k].nNum);
                    if (!bFind)
                    {
                        break;
                    }
                }
                if (bFind)
                {
                    return true;
                }
            }

            sets[nI].bUsed[i] = false;
            sets[nAnsLen - nI].bUsed[j] = false;
        }
    }

    return false;
}

void Search()
{
    for (int i = 0; i <= nAnsLen; ++i)
    {
        if (sets[i].nNum)
        {
            Find(i);
            break;
        }
    }
}

int main()
{
    int nCases;

#ifdef CSU_YX
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    scanf("%d\n", &nCases);

    int nNum = 0;
    int nTotalLen = 0;
    while (gets(szLines[nNum]), nCases)
    {
        if (szLines[nNum][0] == '\0' && nNum != 0)
        {
            nAnsLen = nTotalLen * 2 / nNum;
            memset(szAns, 0, sizeof(szAns));
            Search();
            printf("%s\n\n", szAns);

            memset(sets, 0, sizeof(sets));
            memset(szLines, 0, sizeof(szLines));
            nNum = 0;
            nTotalLen = 0;
            --nCases;
        }
        else if (szLines[nNum][0] != '\0')
        {
            int nLen = strlen(szLines[nNum]);
            nTotalLen += nLen;
            strcpy(sets[nLen].szLines[sets[nLen].nNum], szLines[nNum]);
            ++sets[nLen].nNum;
            ++nNum;
        }
    }

    return 0;
}

无穷大数组上如何直接寻址来实现字典？

发表于 2012-03-20 分类于算法阅读次数： Valine：
本文字数： 1.9k 阅读时长 ≈ 2 分钟

这是算法导论习题11.1-4。
具体题目如下：

解决该题目的要点：
1.由于是无穷大的数组，所以无法事先初始化该数组。
2.所提供的方案必须是O（1）。
3.使用的额外空间只能是O（n），这样平均到每一个项上的空间都是O（1）。

一时之间好像没有一点头绪，在几个群里面发问了，网上搜了很久也没有找到答案，后面一群里有个高人给了个链接，里面有解法。链接地址：

http://www.cnblogs.com/flyfy1/archive/2011/03/05/1971502.html

这篇文章里面另外给了个pdf，这个pdf估计是解法的来源。伪代码写得不给力，不过前面的英文描述却很清晰。说实话，这个方法很巧妙。

解法大概的意思如下：
开一个额外的数组A，A[0]表示A数组元素的数目(当然不包括A[0]本身)，A[i]代表插入的第i个元素的key。假设原来的无穷大数组用Huge
表示，如果Hugei有效，则表示其在A数组中的索引。那么如果A[Huge[i]] == i 而且 Huge[i] <= A[0] &&
Huge[i] > 0，则表示i这个位置已经有元素插入了。

插入：A[0]++;A[A[0]] = key; Huge[key] = A[0];
搜索: A[Huge[i]] == i && Huge[i] <= A[0] && Huge[i] > 0 则return true;
删除: 先搜索该位置是否有元素, 如果Search(key)成功，则先把Huge[ A[A[0]] ] = Huge[key]，
然后交换A[A[0]]和A[Huge[key]]，A[0]—即可。
所有操作都是O（1），平均到每一个项，使用的空间都是O（1）。

我用代码实现的模拟如下：

#include <stdio.h>
#include <vector>
#include <algorithm>
using std::swap;
using std::vector;
#define INF (100)

int nHuge[INF];//假设这个巨大的数组是无法初始化的
vector<int> vA;

void Init()
{
    vA.push_back(0);//添加A[0]表示元素的数目
}

void Insert(int nKey)
{
    vA[0]++;
    nHuge[nKey] = vA[0];
    vA.push_back(nKey);
}

bool Search(int nKey)
{
    if (nHuge[nKey] > 0 && nHuge[nKey] <= vA[0] && vA[nHuge[nKey]] == nKey)
    {
        return true;
    }

    return false;
}

void Delete(int nKey)
{
    if (Search(nKey))
    {
        nHuge[ vA[vA[0]] ] = nHuge[nKey];//将huge的最后一个元素中存储的A数组的索引改为nHuge[nKey]
        swap(vA[vA[0]], vA[nHuge[nKey]]);//交换key
        --vA[0];
        vA.erase(vA.end() - 1);
    }
}

#define MAX (10)
int main()
{
    Init();
    int i;
    for (i = 0; i < MAX; ++i)
    {
        Insert(i);
    }
    for (i = 0; i < MAX; ++i)
    {
        printf("Search:%d %s\n", i, Search(i) == true? "Success" : "Failure");
    }
    printf("\n");

    Delete(4);
    Delete(9);
    Delete(1);
    for (i = 0; i < MAX * 2; ++i)
    {
        printf("Search:%d %s\n", i, Search(i) == true? "Success" : "Failure");
    }

    return 0;
}

CSU OJ - 1183: 计算表达式的值

发表于 2012-03-19 分类于算法，算法题阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

题目意思很简单就是计算含括号的四则运算表达式的值。这个题目很坑爹，刚做的时候，题目描述里面只说里面会有空格，后面居然把题目描述改了。所以，这个题无论怎么改，都是不对。因为，不知道是哪个坑爹的出题人，把数据里面加了\t，难道出题人以为\t也是空格。估计，后面修改题目描述，也是发现这个问题后才改的。这可是还是哥了，改了无数多遍，不处理非法数据就超时，略过非常数据当然直接WA了。好坑爹。
计算表达式的值，以前严蔚敏书上就说用栈构造出来后缀表达式后再计算值。但是这个方法未免太那个了，首先太麻烦了，虽然算法思路不麻烦。我的做法是直接递归计算即可。碰到左括号递归计算新的表达式，右括号作为函数终止条件。否则，按照四则运算的优先级计算当前的表达式。递归算法中需要记录前一个运算符合的优先级，如果前一个运算符的优先级比现在碰到的运算符的优先级高，那么就应该直接返回答案了，当前碰到的运算符的计算交给下一次循环好了。

代码如下：

#include <stdio.h>
#define MAX (100 + 10)
char szData[MAX];

void TrimSpace(char* pszData)
{
    char* pszRead = pszData;
    char* pszWrite = pszData;
    while (*pszRead)
    {
        //由于数据中有\t,与先前题目描述不符合,不处理掉就直接超时了
        if (*pszRead != ' ' && *pszRead != '\t')
        {
            *pszWrite++ = *pszRead;
        }
        ++pszRead;
    }
    *pszWrite = '\0';
}

//nKind代表前一个运算符合的优先级,开始时是0,+-是1,*/是2
double Cal(char*& pszData, int nKind)
{
    double fAns = 0.0;
    while (*pszData && *pszData != ')')//表达式终止的条件是到达'\0'或者碰到右括号
    {
        if (*pszData >= '0' && *pszData <= '9')
        {
            fAns = 10 * fAns + *pszData - '0';
            ++pszData;
        }
        else if (*pszData == '+')
        {
            if (nKind >= 1)
            {
                return fAns;
            }
            ++pszData;
            fAns += Cal(pszData, 1);
        }
        else if (*pszData == '-')
        {
            if (nKind >= 1)
            {
                return fAns;
            }
            ++pszData;
            fAns -= Cal(pszData, 1);
        }
        else if (*pszData == '*')
        {
            if (nKind >= 2)
            {
                return fAns;
            }
            ++pszData;
            fAns *= Cal(pszData, 2);
        }
        else if (*pszData == '/')
        {
            if (nKind >= 2)
            {
                return fAns;
            }
            ++pszData;
            fAns /= Cal(pszData, 2);
        }
        else if (*pszData == '(')
        {
            ++pszData;
            fAns = Cal(pszData, 0);
            ++pszData;//移到')'后面
            return fAns;//一个括号内的是一个完整的表达式,因此直接返回
        }
    }

    return fAns;
}

int main()
{
    while (gets(szData))
    {
        TrimSpace(szData);
        char* pszData = szData;
        printf("%.4f\n", Cal(pszData, 0));
    }
}

一个递归函数能计算出表达式的值，而且能处理优先级和括号，如果是以前的话，我应该是写不出来的。再把算法的实现细节改改，应该也能计算出浮点数的表达式了。

hdu - 1225:Football Score

发表于 2012-03-14 分类于算法，算法题阅读次数： Valine：
本文字数： 2.3k 阅读时长 ≈ 2 分钟

这是个简单的字符串处理题目。看题目，数据应该不是很大，直接暴力处理可以过。如果为了加快搜索速度，在中间输入过程中排序，再二分很麻烦，速度也快不了多少，因为只是输入的过程中需要查找。但是，这个题其实很好用map做，代码量可以少很多，也很简洁。
写这篇blog的目的是为了提醒自己，容易题再这样错下去，真的很伤人心，学什么都没必要了，当时打算继续搞ACM的目的之一就是为了提高代码正确率。这个题，不仅细节部分没看清楚，而且写代码时候把比较函数里面的one.nLost写成了one.nGet，查错了1个多小时，还让队友帮忙查错了好久，真的很无语。写程序确实可以debug，但是这也让我养成了很严重的依赖debug的习惯。
人生不可以debug，人生不可以重来。记得以前很多次很多事情就是开始无所谓，后面悲催到底，无限后悔。

代码如下：

#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#define MAX (100)
using std::map;
using std::string;
using std::vector;
using std::sort;

struct INFO
{
    INFO()
    {
        nScore = nGet = nLost = 0;
    }

    string strName;
    int nScore;
    int nGet;
    int nLost;
    bool operator < (const INFO& one) const
    {
        if (nScore != one.nScore)
        {
            return nScore > one.nScore;
        }
        else if (nGet - nLost != one.nGet - one.nLost)//这里把one.nLost写成了one.nGet
        {
            return nGet - nLost > one.nGet - one.nLost;
        }
        else if (nGet != one.nGet)
        {
            return nGet > one.nGet;
        }
        else
        {
            return strName < one.strName;
        }
    }
};

int main()
{
    int nN;

    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    while (scanf("%d", &nN) == 1)
    {
        int nLast = nN * (nN - 1);
        char szOne[MAX];
        char szTwo[MAX];
        int nOne, nTwo;

        map<string, INFO> myMap;
        for (int i = 0; i < nLast; ++i)
        {
            scanf("%s %*s %s %d:%d", szOne, szTwo, &nOne, &nTwo);
            //printf("%s %s %d %d\n", szOne, szTwo, nOne, nTwo);

            string strOne = szOne;
            myMap[strOne].strName = strOne;
            myMap[strOne].nGet += nOne;
            myMap[strOne].nLost += nTwo;

            string strTwo = szTwo;
            myMap[strTwo].strName = strTwo;
            myMap[strTwo].nGet += nTwo;
            myMap[strTwo].nLost += nOne;

            if (nOne > nTwo)
            {
                myMap[strOne].nScore += 3;
            }
            else if (nOne == nTwo)
            {
                myMap[strOne].nScore += 1;
                myMap[strTwo].nScore += 1;
            }
            else
            {
                myMap[strTwo].nScore += 3;
            }
        }

        map<string, INFO>::iterator it;
        vector<INFO> myVt;
        for (it = myMap.begin(); it != myMap.end(); it++)
        {
            myVt.push_back(it->second);
        }

        sort(myVt.begin(), myVt.end());
        for (int i = 0; i < myVt.size(); ++i)
        {
            printf("%s %d\n", myVt[i].strName.c_str(), myVt[i].nScore);
        }
        printf("\n");
    }

    return 0;
}

两个栈实现一个队列和两个队列实现一个栈

发表于 2012-03-11 分类于算法阅读次数： Valine：
本文字数： 3.3k 阅读时长 ≈ 3 分钟

两个栈实现一个队列
要求：只能使用栈的pop和push，以及测试栈是否为空三个操作。
实现思路：
队列里面使用stack one 和 stack two。
进队列时，直接进入栈one即可。
出队列时，从two弹出一个元素，如果two里面的元素为空，则将one里面的元素依次弹出并压入two中，再从two弹出一个元素返回。

用STL里面的stack模拟实现queue的代码如下：


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stack>
using std::stack;

template<class T> class CQueue
{
public:
    CQueue()
    {
        nSize = 0;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        one.push(t);
        ++nSize;
    }

    void pop()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        two.pop();
        --nSize;
    }

    T& front()
    {
        if (two.empty())
        {
            while (!one.empty())
            {
                two.push(one.top());
                one.pop();
            }
        }
        return two.top();
    }

    T& back()
    {
        return one.top();
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    stack<T> one;
    stack<T> two;
    int nSize;
};

#define MAX 20

int main()
{
    CQueue<int> q;

    srand(time(NULL));
    for (int i = 0; i < MAX; ++i)
    {
        q.push(i);

        if (rand() % 2)
        {
            printf("front: %d\n", q.front());
            q.pop();
        }
    }

    while (!q.empty())
    {
        printf("front: %d\n", q.front());
        q.pop();
    }

    return 0;
}

两个队列实现一个栈
要求：只能使用从队列的尾部入和头部出，以及测试队列是否为空三个操作。
实现思路：
队列里面使用queue one 和 stack two。
进栈时，根据当前元素是全部存储在哪个队列而选择从one或者two的尾部进入。
出栈时，假设当前元素都存储在one里面，则不断出队列，直到队列为空之前的所有元素一次进入队列two，而one里面的最后一个元素作为栈弹出的值返回。
对于当前元素是存储在哪个队列里面，可以设置变量标记，初始化时候存储在one里面，操作一次，由于元素要倒转，则存储位置会变一次。

用STL里面的queue模拟实现的stack代码如下：


#include <stdio.h>
#include <queue>
using std::queue;

template<class T> class CStack
{
public:
    CStack()
    {
        nSize = 0;
        nTime = 1;
    }

    void clear()
    {
        while (!one.empty())
        {
            one.pop();
        }
        while (!two.empty())
        {
            two.pop();
        }
    }

    void push(const T& t)
    {
        if (nTime % 2)
        {
            one.push(t);
        }
        else
        {
            two.push(t);
        }
        ++nSize;
    }

    void pop()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
            }
        }

        nTime = (nTime + 1) % 2;
        --nSize;
    }

    T& top()
    {
        if (nTime % 2)
        {
            while (!one.empty())
            {
                T t = one.front();
                one.pop();
                if (!one.empty())
                {
                    two.push(t);
                }
                else
                {
                    two.push(t);
                    nTime = (nTime + 1) % 2;
                    return two.back();
                }
            }
        }
        else
        {
            while (!two.empty())
            {
                T t = two.front();
                two.pop();
                if (!two.empty())
                {
                    one.push(t);
                }
                else
                {
                    one.push(t);
                    nTime = (nTime + 1) % 2;
                    return one.back();
                }
            }
        }
    }

    bool empty()
    {
        return nSize == 0;
    }

private:
    queue<T> one;
    queue<T> two;
    int nSize;
    int nTime;
};

#define MAX 20

int main()
{
    CStack<int> stack;

    for (int i = 0; i < MAX; ++i)
    {
        stack.push(i);
    }

    while (!stack.empty())
    {
        printf("top: %d\n", stack.top());
        stack.pop();
    }

    return 0;
}

邮局位置问题和带权中位数

发表于 2012-03-11 分类于算法阅读次数： Valine：
本文字数： 498 阅读时长 ≈ 1 分钟

带权中位数定义如下：

邮局位置问题定义如下：

上一篇文章输油管道问题里面证明了，当权值Wi都为1的时候，中位数就是最佳的解。但是，现在Wi已经不一定是1了。所以，现在
需要证明在任意Wi的取值情况下，带权中位数能够成为邮局位置的最佳解。假设，所有Wi都是1的倍数，如果是小数的话，可以所有的
Wi都乘以一定的倍数。那么wid(p,pi) = Σ(p,pi)(i从1到wi)，这个意思是把距离乘以了wi倍。
但是，现在可以换一种看法，换成了pi位置有wi个重合的点，且每一个点的权值都是1，那么其和也是wid(p,pi)。那么对所有的pi
都这样分解，就把问题重新转换成了输油管道问题了。输油管道问题的最优解就是中位数，那么邮局问题的最优解就是转换之后的
这些点的中位数点。而这个点一定存在于带权中位数那个点分解出的一堆点中。
二维邮局问题的解法是把x和y分开求2次一维邮局问题，然后把解组和起来，得到答案。

求带权中位数的算法比较简单，直接的做法是，先把n个点按照位置排序，然后按点的位置从小到大遍历，找到满足要求的点即可。
不算排序点位置的预处理，因为很多时候点应该就是按顺序给出的，所以其时间复杂度是O(n)。
要求：

输油管道问题(POJ - 1723)

发表于 2012-03-09 分类于算法，算法题阅读次数： Valine：
本文字数： 2k 阅读时长 ≈ 2 分钟

先看算导上输油管道问题的描述：

这个题，虽然说给出了井的x,y坐标，但是要修建的主管道却只是一条横向的，而且其余管道也只是到这条管道的竖向距离。那么，就转换为确定一条直线 y = m，使得其它个点到这条直线的距离最多。也许不需要多的提示，大家的直觉就会想到应该所有y值的中点。但是，这个的证明却不是那么的明显。

证明如下：
设所有的y值系列为y1,y2,…,yn，并且假设这个是按递增排列的。我们要求的是Sum = Σ|yi-m|(1<=i<=n),

1）显然假如选小于y1或者大于yn的y=m都不会比选y1或者yn更好。
2）如果选y1或者yn，那么|y1-m|+|yn-m| = |yn-y1|都是一样的结果，甚至选y1和yn之间的任意一个值。
3）如此继续下去，对于y2和yn，也有2）所描述的性质
4）继续到最后，只需要取最中间一对点之间的值即可，如果n是奇数，那么就是中间的点，如果n是偶数，取任意一个中间点都可以。

通过上面证明，我们可以选取第y(n/2 + 1)作为修建主管道的地方。当然这可能是唯一的最优选择，或者无数个最优选择中的一个。那么现在已经转换为求中位数了，求中位数的办法最简单的是对序列排序然后取中间的即可。算法导论上有一种平均代价O(n)的办法，思路类似于快速排序，快排的每一次操作都是划分数组，前小后大，如果我们也这一次次去划分数组，刚好轴元素处于我们要求的那个位置上那么就达到我们的目的了，下面的代码中Select函数就是求一个数组的中位数。

对于POJ 1723题，很显然y的选择是中位数即可，x的选择需要转换一下也变成求中位数了。题目中描述，最后要达到的效果是每个士兵都占成一横排，而且彼此相邻，也就是y相同，但是x系列k,k+1,k+2,…,k+n-1。那么如何从原来的x0,x1,x2,…,x(n-1)移动过去了。可以简单的考虑下，将最左边的士兵移动到k,次左的移动到k+1,…,最右边的移动到k+n-1，所需要的移动之和一定是最小的。那么我们可以将原来的x0-x(n-1)排序，得到x’0,x’1,…,x’(n-1),要求的Sum = **Σ|x’i - (k + i)| = Σ|(x’i - i) - k|**,那么要使Sum最小，只需要求序列X’i - i的中位数即可了。

#include <stdio.h>
#include <algorithm>
using std::sort;
using std::swap;
#define MAX (10000 + 10)
int Partion(int* pnA, int nLen)
{
    int i, j;
    for (i = j = 0; i < nLen - 1; ++i)
    {
        if (pnA[i] < pnA[nLen - 1]) { swap(pnA[i], pnA[j++]); } } swap(pnA[j], pnA[nLen - 1]); return j; } int Select(int* pnA, int nLen, int nIndex) { if (nLen > 1)
    {
        int nP = Partion(pnA, nLen);
        if (nP + 1 == nIndex)
        {
            return pnA[nP];
        }
        else if (nP + 1 > nIndex)
        {
            return  Select(pnA, nP, nIndex);
        }
        else
        {
            return Select(pnA + nP + 1, nLen - nP - 1, nIndex - nP - 1);
        }
    }
    else
    {
        return pnA[0];
    }
}
int main()
{
    int nX[MAX];
    int nY[MAX];
    int nN;
    int i;
    while (scanf("%d", &nN) == 1)
    {
        for (i = 0; i < nN; ++i)
        {
            scanf("%d%d", &nX[i], &nY[i]);
        }
        int nMY = Select(nY, nN, nN / 2 + 1);
        sort(nX, nX + nN);
        for (i = 0; i < nN; ++i)
        {
            nX[i] = nX[i] - i;
        }
        int nMX = Select(nX, nN, nN / 2 + 1);
        int nSum = 0;
        for (i = 0; i < nN; ++i)
        {
            nSum += abs(nX[i] - nMX);
            nSum += abs(nY[i] - nMY);
        }
        printf("%d\n", nSum);
    }

    return 0;
}

快排的一种简易写法

发表于 2012-03-03 分类于算法阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

虽然简易二字，因人而异。不过，写一个快排确实并不需要过20行，超过几分钟时间的代码。面试的时候，面试官确实会经常问起快排什么的。但是，大家上的入门课基本是使用严蔚敏老奶奶的教材，上面对于快排的讲解我是不敢恭维的。至少上面关于快排的写法，我是写过好几次之后都是没掌握好的。后面，应该是看K&R的c语言程序设计时候，发现一种更简便的partion方法，但是当时我也没怎么掌握。这一切直到，寒假认真阅读算法导论的时候。

不用算法牛人，算法学得好或者对快排理解深刻的，不用把这篇文章看完了，相信你们都能在10分钟之内写一个正确的快排了。
废话少说，还是来讲讲如何保证10分钟之内写一个正确的快排，而且以后都能10分钟之内写出来，而不是此刻看了我说的这些胡言之后。

快排的主函数大家都会，现在我给个简易点的样子：

void QuickSort(int* pnA, int nLen)
{
    if (nLen > 1)
    {
        int nP = Partion(pnA, nLen);
        QuickSort(pnA, nP);//排序第nP+1个元素前面的nP个元素
        QuickSort(pnA + nP + 1, nLen - nP - 1);//排序第nP+1个元素后面的元素
    }
}

那么现在就剩下Partion函数了。
我记得严蔚敏书上的写法中Partion 函数里面是有几个循环的。而且即使大概写出来了，也很难处理正确边界。
现在，我要说的就是算法导论上，作为教材内容出现的Partion函数。还是看代码吧。

int Partion(int* pnA, int nLen)
{
//这里选择最后一个元素作为轴元素
    int i, j;
    for (i = j = 0; i < nLen - 1; ++i)
    {
        if (pnA[i] < pnA[nLen - 1])
        {
            swap(pnA[i], pnA[j];//交换2个数的函数，大家都能写吧，stl中也有
            ++j;
        }
    }
    swap(pnA[j], pnA[nLen - 1]);
    return j;
}

为了公平起见，上面的代码我都是在blog上面直接敲的，写这10多行代码是绝对用不了10分钟的。主递归函数大家都会写，Partion函数里面只有一个for循环，所以只要明确了for循环的意思，快排的速写就迎刃而解了。其实，按照算导的说法，这个for一直在划分区间。区间[0,j-1]是小于最后一个元素的区间，[j,nLen - 2]是大于等于最后一个元素的区间，所以最后将第nLen-1个元素与第j个元素交换即可，Partion应该返回的值也应该是j。
我不知道大家理解上面那句黑体字的话没，如果理解了，随便写个快排是没问题了。至少，可能的下次面试时候，可以潇洒地写个快排给面试官看看了，虽然这也许并不是什么值得庆幸的事情。

算法导论里面的快速排序那章后面还有思考题，其中第一个思考题，提出的另外一种叫做Hoare划分的partion写法，意思就和严蔚敏书上的partion函数一致的。理解的关键是，轴元素一直处于被交换中。只要发现了这点，写一两次后，这种partion方法也能掌握好了，不过写起来是循环嵌循环了，没那么舒服。

如何生成均匀随机排列(等概率生成排列)

发表于 2012-02-26 分类于算法阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

这个算法的应用，比如洗牌，这个大家都非常熟悉。很久以前用的是最原始的方法，就是一直rand()未出现的牌，直至生成所有的牌。这当然是一个while(1)循环，很烂的算法吧。后面听说直接交换牌，打乱即可了。但是打乱后生成的排列是随机的么，是等可能随机的么。
其实，这个问题上算法导论上早已经有了答案了，看过算法导论之后觉得没看之前真的是算法修养太差了。
算法的伪代码如下图所示：

具体c++实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>
// void Swap(int& nOne, int& nTwo)
// {
//  nOne = nOne + nTwo;
//  nTwo = nOne – nTwo;
//  nOne = nOne – nTwo;
// }
void Swap(int&  nOne, int&  nTwo)
{
    int nTemp;
    nTemp = nOne;
    nOne = nTwo;
    nTwo = nTemp;
}
//返回一个在区间[nBeg, nEnd]内的随机数
int Random(int nBeg, int nEnd)
{
    assert(nEnd >= nBeg);
    if (nBeg == nEnd)
    {
        return nBeg;
    }
    else
    {
        return rand() % (nEnd – nBeg + 1) + nBeg;
    }
}
void RandomizeInPlace(int* pnA, int nLen)
{
    static bool s_bFirst = false;
    if (!s_bFirst)
    {
        srand(time(NULL));
        s_bFirst = true;
    }
    for (int i = 0; i < nLen; ++i)
    {
        Swap(pnA[i], pnA[Random(i, nLen - 1)]);
    }
}
int main()
{
    int nArray[20];
    int i, j;
    for (i = 1; i <= 20; ++i)
    {
        int nCnt = i;
        while (nCnt–)
        {
            for (j = 0; j < i; ++j)
            {
                nArray[j] = j;
            }
            RandomizeInPlace(nArray, i);
            for (j = 0; j < i; ++j)
            {
                printf("%d", nArray[j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

运行效果图片如下：

根据运行结果大致就可以感觉到，生成的排列都是随机的。
这里要多说一句那就是我注释的那个交换函数其实是有bug的，也许这才是不提倡使用这个交换方法的真正原因，而不仅仅是难以理解。用同一个变量去调用该函数，会将该变量置0，而不是保持原来的值！！！至于如何证明这个算法生成的均匀随机的排列，可以参考算法导论5.3节最后一部分。
证明的大致思路是利用循环不变式的证明方法：证明i次循环后得到某个排列的概论是(n -i)! / n!，那么n次循环后得到最终那个排列的
概论就是1/n!，这样就证明了该算法能够得到均匀随机排列。
这个算法其实就是随机化算法的一种，其实快排也有所谓的随机化版本，改动的地方只是随机选择了中轴元素而已，这个在算法导论上也有介绍。

自定义可变参数函数BatchDelFile, 调用cmd批量删除指定格式文件, Windows界面下不回显Console窗口

发表于 2012-01-03 分类于 MFC 阅读次数： Valine：
本文字数： 4k 阅读时长 ≈ 4 分钟

今天在做课设，由于想给程序加上删除以前的配置文件的功能，由于某种原因，同类型的文件比较多，加上暑假实习的时候，做了个用dir命令实现的批量文件修改器，所以决定用del命令，一下子写好后，发现以前由于没有要求做界面，而现在课设我用的是MFC里面的CFormView做的界面，所以会闪烁而过一个console窗口，实在不爽之，所以，找方法去掉它。
网上找来找去，只找到启动cmd，传参数的都很少，传参数时候组合参数的更加少，加上我对dos命令不熟悉，所以实在悲催，浪费了不少时间。
这种东西，一直窃以为有人做好之后，提供比较合格的接口，大家以后都方便，所以贴出来，大家雅俗共赏，批评下。还发现网上的代码有个问题，居然大多把直接cmd路径写上去，其实大家都知道，系统路径是不确定的，所以特定修正了这个bug，而且我也实验了下，无论参数是绝对路径还是相对路径这个函数都是有效的。
大家用这个函数的时候，记得cmd命令都是可以匹配通配符的哦。

函数代码如下:

//批量删除指定格式文件,不显示console窗口

void BatchDelFile(char* pszFile)
{
    char szDelCmd[MAX_INFO_LEN];
    char szCurDir[MAX_PATH];
    char szCmdPath[MAX_PATH];
    SHELLEXECUTEINFO shExecInfo = {0};

    GetCurrentDirectory(MAX_PATH, szCurDir);//获取当前路径
    GetSystemDirectory(szCmdPath, MAX_PATH);//获取cmd路径
    strcat(szCmdPath, "\\cmd.exe");
    sprintf(szDelCmd, "%s /c del /f /q /s %s",
    szCmdPath, pszFile);//格式化出命令字符串, 注意加上/c, 还有那2个""

    shExecInfo.cbSize = sizeof(SHELLEXECUTEINFO);
    shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
    shExecInfo.hwnd = NULL;
    shExecInfo.lpVerb = NULL;
    shExecInfo.lpFile = szCmdPath;//cmd的路径
    shExecInfo.lpParameters = szDelCmd;//程序参数,参数格式必须保证正确
    shExecInfo.lpDirectory = szCurDir;//如果szFile是相对路径,那个这个参数就会起作用
    shExecInfo.nShow = SW_HIDE;//隐藏cmd窗口
    shExecInfo.hInstApp = NULL;
    ShellExecuteEx(&shExecInfo);
    WaitForSingleObject(shExecInfo.hProcess, INFINITE);//无限等待cmd窗口执行完毕
}

以下是我在一个消息出来函数的调用：
char szDelFiles[MAX_PATH];
sprintf(szDelFiles, “\”.tcp.txt\” + \”.udp.txt\””);
BatchDelFile(szDelFiles);

为了调用方便，我还实现了一个可变参数列表的版本，以及一个传一个文件名数组的版本。

可变参数版本代码如下：
//批量删除指定格式文件,不显示console窗口

void BatchDelFile(int nNum, ...)
{
    va_list argPtr;
    int i;
    char* pszDelCmd;
    char szCurDir[MAX_PATH];
    char szCmdPath[MAX_PATH];
    SHELLEXECUTEINFO shExecInfo = {0};

    pszDelCmd = (char*)malloc((nNum + 2)* MAX_PATH);
    GetCurrentDirectory(MAX_PATH, szCurDir);//获取当前路径
    GetSystemDirectory(szCmdPath, MAX_PATH);//获取cmd路径
    strcat(szCmdPath, "\\cmd.exe");
    sprintf(pszDelCmd, "%s /c del /f /q /s ", szCmdPath);//格式化出命令字符串, 注意加上/c
    va_start(argPtr, nNum);
    for(i = 0; i < nNum; ++i)
    {
        strcat(pszDelCmd, "\"");
        strcat(pszDelCmd, *(char**)argPtr);
        strcat(pszDelCmd, "\"");
        if (i != nNum - 1)
        {
            strcat(pszDelCmd, " + ");
        }
        va_arg(argPtr, char**);
    }
    va_end(argPtr);
    shExecInfo.cbSize = sizeof(SHELLEXECUTEINFO);
    shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
    shExecInfo.hwnd = NULL;
    shExecInfo.lpVerb = NULL;
    shExecInfo.lpFile = szCmdPath;//cmd的路径
    shExecInfo.lpParameters = pszDelCmd;//程序参数,参数格式必须保证正确
    shExecInfo.lpDirectory = szCurDir;//如果szFile是相对路径,那个这个参数就会起作用
    shExecInfo.nShow = SW_HIDE;//隐藏cmd窗口
    shExecInfo.hInstApp = NULL;
    ShellExecuteEx(&shExecInfo);
    WaitForSingleObject(shExecInfo.hProcess, INFINITE);//无限等待cmd窗口执行完毕
    free(pszDelCmd);
}

调用方法：
BatchDelFile(2, “.tcp.txt”, “.udp.txt”);//第一个是文件个数，后面依次是文件路径，文件路径可以是相对路径也可以是绝对路径。

文件名数组的版本代码如下：

void BatchDelFile(int nNum, char** pszFiles)
{
    int i;
    char* pszDelCmd;
    char szCurDir[MAX_PATH];
    char szCmdPath[MAX_PATH];
    SHELLEXECUTEINFO shExecInfo = {0};

    pszDelCmd = (char*)malloc((nNum + 2)* MAX_PATH);
    GetCurrentDirectory(MAX_PATH, szCurDir);//获取当前路径
    GetSystemDirectory(szCmdPath, MAX_PATH);//获取cmd路径
    strcat(szCmdPath, "\\cmd.exe");
    sprintf(pszDelCmd, "%s /c del /f /q /s ", szCmdPath);//格式化出命令字符串, 注意加上/c

    for(i = 0; i < nNum; ++i)
    {
        strcat(pszDelCmd, "\"");
        strcat(pszDelCmd, *(pszFiles + i));
        strcat(pszDelCmd, "\"");
        if (i != nNum - 1)
        {
            strcat(pszDelCmd, " + ");
        }
    }
    shExecInfo.cbSize = sizeof(SHELLEXECUTEINFO);
    shExecInfo.fMask = SEE_MASK_NOCLOSEPROCESS;
    shExecInfo.hwnd = NULL;
    shExecInfo.lpVerb = NULL;
    shExecInfo.lpFile = szCmdPath;//cmd的路径
    shExecInfo.lpParameters = pszDelCmd;//程序参数,参数格式必须保证正确
    shExecInfo.lpDirectory = szCurDir;//如果szFile是相对路径,那个这个参数就会起作用
    shExecInfo.nShow = SW_HIDE;//隐藏cmd窗口
    shExecInfo.hInstApp = NULL;
    ShellExecuteEx(& shExecInfo);
    WaitForSingleObject(shExecInfo.hProcess, INFINITE);//无限等待cmd窗口执行完毕
    free(pszDelCmd);
}

调用方法：

char* szFiles[2];
szFiles[0] = "*.tcp.txt";
szFiles[1] = "*.udp.txt";
BatchDelFile(2, szFiles);