STEP BY STEP

发表于 分类于 阅读次数： 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)。
要求：

发表于 分类于 ， 阅读次数： 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的中位数即可了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#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;
}

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

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

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

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

1
2
3
4
5
6
7
8
9
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函数。还是看代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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方法也能掌握好了，不过写起来是循环嵌循环了，没那么舒服。

发表于 分类于 阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

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

具体c++实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#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!，这样就证明了该算法能够得到均匀随机排列。
这个算法其实就是随机化算法的一种，其实快排也有所谓的随机化版本，改动的地方只是随机选择了中轴元素而已，这个在算法导论上也有介绍。

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

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

函数代码如下:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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”);//第一个是文件个数，后面依次是文件路径，文件路径可以是相对路径也可以是绝对路径。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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);
}

调用方法：

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

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.1k 阅读时长 ≈ 3 分钟

题目1描述:
输入:一个序列s,该序列里面可能会有同样的字符,不一定有序
输出:打乱输入中的序列,可能产生的所有新的序列
题目2描述:

输入:一个序列s,该序列里面可能会有同样的字符,不一定有序 和 一个整数k
输出:该序列往后计算第k个序列,所有序列是以字典序排序的如果会有序搜索的童鞋自然而然能立刻做出来第一个题目,可是第二个题目在s较长的情况下,却需要用模拟而不是搜索…
大家都知道STL里面有个泛函模版, prev_permutation和next_permutation,用法也很简单,实现的就是题目2的功能…
但是算法最好得靠自己想出来,自己想出来的才是自己的,碰到新的问题才能产生思想的火花…废话少说,题目1的解法就是深搜,不过需要加上一个bool数组标记和一个函数确定不同字符之间的大小(有可能这个大小还不是Ascii码就能决定的),
大致描述下搜索过程,比如输入序列是12345,那么我搜索的过程大致是第一层按顺序选取1-5,进入第二层的时候也是按顺序选取1-5,
以此类推,但是每一层里面都只能选前面的层次没有选过的数,而且因为有重复字符,算法还必须保证每一层里面按顺序选取的字符必须是升序的,
熟悉顺序搜索和回溯的同学,很自然就会产生这样的想法…
POJ - 1256的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>
#include <algorithm>
#define MAX (13 + 10)
using namespace std;
bool bUsed[MAX];
char szAns[MAX];
char szInput[MAX];
bool CmpChar(char chOne, char chTwo)
{
    if (abs(chOne - chTwo) != 'a' - 'A')
    {
        return tolower(chOne) - tolower(chTwo) < 0;
    }
    return chOne - chTwo < 0;
} 

bool Greater(char chOne, char chTwo) 
{ 
    if (abs(chOne - chTwo) != 'a' - 'A') 
    { 
        return tolower(chOne) - tolower(chTwo) > 0;
    }
    return chOne - chTwo > 0;
}

void Gen(int nDepth, int nLen)
{
    if (nDepth == nLen)
    {
        szAns[nLen] = '\0';
        printf("%s\n", szAns);
        return;
    }

    char chLast = '\0';
    for (int i = 0; i < nLen; ++i)
    {
        if (!bUsed[i] && Greater(szInput[i], chLast))
        {
            bUsed[i] = true;
            szAns[nDepth] = szInput[i];
            Gen(nDepth + 1, nLen);
            bUsed[i] = false;
            chLast = szInput[i];
        }
    }
}
int main()
{
    int nCases;

    scanf("%d", &nCases);
    while (nCases--)
    {
        scanf("%s", szInput);
        int nLen = strlen(szInput);
        sort(szInput, szInput + nLen, CmpChar);
        Gen(0, nLen);
    }

    return 0;
}

题目2的解法是模拟,功能类似与STL的那2个泛型模版函数,算法的大致过程是想办法从当前序列进入下一个刚好比其大或者刚好比其小的序列…很自然我们想到要把序列后面大的字符交和前面小的字符交换就会使序列变大,为了使其刚好变大,可以把交换后的字符从交换位置起至最后都排序一下,现在的问题是我们如何选取2个字符交换…正确的想法是,我们从最后面开始往前面看,寻找一个最长的递增序列,找到之后,我们只需要选取递增序列前面的那个字符chBefore和递增序列里面的一个最小的比chBefore大的字符交换即可…交换之后,将新的递增序列排序一下即可…
为什么这样做了,因为从后往前看的递增序列,是不能交换2个字符让当前序列变大的,所以必须选取最长递增序列前面的那个字符交换…

POJ百练 - 1833 的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX (1024 + 10)
using namespace std;
int nInput[MAX];
void GetNext(int* nInput, int nLen)
{
    int i = nLen - 2;
    while (i >= 0)
    {
        if (nInput[i] >= nInput[i + 1])
        {
            --i;
        }
        else
        {
            int k = i + 1;
            for (int j = nLen - 1; j > i; --j)
            {
                if (nInput[j] > nInput[i] && nInput[j] < nInput[k])
                {
                    k = j;
                }
            }
            swap(nInput[i], nInput[k]);
            sort(nInput + i + 1, nInput + nLen);
            return;
        }
    }

    sort(nInput, nInput + nLen);
}
int main()
{
    int nCases;
    scanf("%d", &nCases);
    while (nCases--)
    {
        int nLen;
        int nK;
        scanf("%d%d", &nLen, &nK);
        for (int i = 0; i < nLen; ++i)
        {
            scanf("%d", &nInput[i]);
        }
        for (int i = 0; i < nK; ++i)
        {
            GetNext(nInput, nLen);
        }
        for (int i = 0; i < nLen; ++i)
        {
            printf("%d%s", nInput[i], i == nLen - 1 ? "\n" : " ");
        }
    }
    return 0;
}

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.3k 阅读时长 ≈ 1 分钟

链接: http://poj.grids.cn/practice/2774

这个题可以用二分解,虽然也有dp的解法。可能用二分解这个题不是很明显,但是确实是可以的。最大的解就是所有的棍子长/要求的棍子数,最小的解是0,直接在其中进行二分即可。这个题属于二分出最大满足条件的解的情况。这个题为什么能够二分了。我是这样想的。首先,解空间确实是有序的吧,从数字0-数字nSum/nK。其次,对于任意一个处于这个范围内的数字,只有满足和满足题目要求2种情况,那么和我们二分数字有什么区别了,我们二分一个有序数组,看里面有没有某个数字,是不是也只要判断下nMid满足是否条件是吧。所以,这个题是可以二分的。二分的条件就是解空间有序的,或者可以方便在解空间里面跳跃。而且这个题的二分还需要点技巧,因为是查找满足条件的最大解。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include 
#include 
#include 
#define MAX (10000 + 10)
using namespace std;
int nN, nK;
int nWoods[MAX];
bool IsAnsOk(int nAns)
{
    if (nAns == 0)
    {
        return true;
    }
    else
    {
        int nTotal = 0;
        for (int i = nN - 1; i >= 0; --i)
        {
            nTotal += nWoods[i] / nAns;
            if (nTotal >= nK)
            {
                return true;
            }
        }
        return false;
    }
}
int SearchAns(int nMax)
{
    int nBeg = 0, nEnd = nMax;
    while (nBeg <= nEnd)
    {
        int nMid = (nBeg + nEnd) / 2;
        if (IsAnsOk(nMid))
        {
            nBeg = nMid + 1;
        }
        else
        {
            nEnd = nMid - 1;
        }
    }
    return nBeg - 1;
}
int main()
{
    while (scanf("%d%d", &nN, &nK) == 2)
    {
        int nSum = 0;
        for (int i = 0; i < nN; ++i)
        {
            scanf("%d", &nWoods[i]);
            nSum += nWoods[i];
        }
        sort(nWoods, nWoods + nN);
        int nMax = nSum / nK;
        printf("%d\n", SearchAns(nMax));
    }
    return 0;
}

所以,只是把==换成了IsAnsOk函数调用而已…而且由于这是查找最大解,返回值做了下变化而已…
仔细分析二分的写法(我的另一篇文章(标题是关于密码的一个解题报告)有说明),
其实写出查找最大解和最小解的二分都不是件麻烦的事情…

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3.7k 阅读时长 ≈ 3 分钟

链接:http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1219

这个题就是求出所有结点的距离之后,再找出某个结点,该结点离其它结点的最大距离是所有结点中是最小的…
解法1:深搜出所有结点间的距离,但是会超时,即使深搜的过程使用中记忆化搜索(就是用2维数组保存已经搜出的答案,如果后面的搜索需要用到直接使用即可)…
解法2:Floyd算法,3重循环直接找出所有结点之间的最短距离
解法3:对每一个结点应用一次迪杰斯特拉算法,找出所有结点与其它结点间的最短距离…

解法2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <string.h>
#define MAX  (100 + 10)
#define INF (1000000 + 10)
int nN, nM;
int nDis[MAX][MAX];
void SearchAll()
{
    for (int k = 0; k < nN; ++k)
    {
        for (int i = 0; i < nN; ++i)
        {   
            for (int j = 0; j < nN; ++j)
            {
                if (nDis[i][k] + nDis[k][j] < nDis[i][j])
                {
                    nDis[i][j] = nDis[j][i] = nDis[i][k] + nDis[k][j];
                }
            }
        }
    }
}
int main()
{
    while (scanf("%d%d", &nN, &nM) == 2)
    {
        for (int i = 0; i < nN; ++i)
        {
            for (int j = 0; j < nN; ++j)
            {
                if (i == j)
                {
                    nDis[i][j] = 0;
                }
                else
                {
                    nDis[i][j] = INF;
                }
            }
        }
        while (nM--)
        {
            int nX, nY, nK;
            scanf("%d%d%d", &nX, &nY, &nK);
            nDis[nX][nY] = nDis[nY][nX] = nK;
        }
        SearchAll();
        bool bOk = false;
        int nMin = 1 << 30;

        for (int i = 0; i < nN; ++i)
        {
            int nTemp = 0;
            int j = 0;
            for ( ; j < nN; ++j) 
            { 
                if (i == j) continue; 
                if (nDis[i][j] == INF) 
                { 
                    break; 
                } 
                else 
                { 
                    if (nDis[i][j] > nTemp)
                    {
                        nTemp = nDis[i][j];
                    }
                }
            }
            if (j == nN)
            {
                bOk = true;
                if (nTemp < nMin)
                {
                    nMin = nTemp;
                }
            }
        }

        if (bOk)
        {
            printf("%d\n", nMin);
        }
        else
        {
            printf("Can not\n");
        }
    }
    return 0;
}

关于Floyd算法,可以这样理解…比如刚开始只取2个结点i,j,它们的距离一定是dis(i,j),但是还有其它结点,需要把其它结点也慢慢加进来,所以最外层关于k的循环意思就是从0至nN-1,把所有其它结点加进来,比如加入0号结点后,距离dis(i,0)+dis(0,j)可能会比dis(i,j)小,如果是这样就更新dis(i,j),然后后面加入1号结点的时候,实际上是在已经加入0号结点的基础上进行的处理了,效果变成dis(i,0,1,j),可能是最小的,而且中间的0,1也可能是不存在的,当然是在dis(i,j)原本就是最小的情况下…
这个算法可以用下面这个图片描述…

解法3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <string.h>
#define MAX  (100 + 10)
#define INF (1000000 + 10)
int nN, nM;
int nDis[MAX][MAX];
void Search(int nSource)
{
    bool bVisit[MAX];
    memset(bVisit, false, sizeof(bVisit));
    bVisit[nSource] = true;
    for (int i = 0; i < nN - 1; ++i)
    {
        int nMin = INF;
        int nMinPos = 0;
        for (int j = 0; j < nN; ++j)
        {
            if (!bVisit[j] && nDis[nSource][j] < nMin)
            {
                nMin = nDis[nSource][j];
                nMinPos = j;
            }
        }
        if (bVisit[nMinPos] == false)
        {
            bVisit[nMinPos] = true;
            for (int j = 0; j < nN; ++j)
            {
                if (nDis[nSource][nMinPos] + nDis[nMinPos][j] < nDis[nSource][j])
                {
                    nDis[nSource][j] = nDis[nSource][nMinPos] + nDis[nMinPos][j];
                }
            }
        }
    }
}
void SearchAll()
{
    for (int k = 0; k < nN; ++k)
    {
        Search(k);
    }
}
int main()
{
    while (scanf("%d%d", &nN, &nM) == 2)
    {
        for (int i = 0; i < nN; ++i)
        {
            for (int j = 0; j < nN; ++j)
            {
                if (i == j)
                {
                    nDis[i][j] = 0;
                }
                else
                {
                    nDis[i][j] = INF;
                }
            }
        }
        while (nM--)
        {
            int nX, nY, nK;
            scanf("%d%d%d", &nX, &nY, &nK);
            nDis[nX][nY] = nDis[nY][nX] = nK;
        }
        SearchAll();
        bool bOk = false;
        int nMin = 1 << 30;
        for (int i = 0; i < nN; ++i)
        {
            int nTemp = 0;
            int j = 0;
            for ( ; j < nN; ++j) 
            { 
                if (i == j) continue; 
                if (nDis[i][j] == INF) 
                { 
                    break;
                } 
                else
                { 
                    if (nDis[i][j] > nTemp)
                    {
                        nTemp = nDis[i][j];
                    }
                }
            }
            if (j == nN)
            {
                bOk = true;
                if (nTemp < nMin)
                {
                    nMin = nTemp;
                }
            }
        }
        if (bOk)
        {
            printf("%d\n", nMin);
        }
        else
        {
            printf("Can not\n");
        }
    }
    return 0;
}

迪杰斯特拉算法的核心思想是维护一个源点顶点集合,任何最短路径一定是从这个顶点集合发出的…
初始化时,这个集合就是源点…
我们从该其它结点中选出一个结点,该结点到源点的距离最小…
显然,这个距离就是源点到该结点的最短距离了,我们已经找到了答案的一部分了…然后,我们就把该结点加入前面所说的顶点集合…
现在顶点集合更新了,我们必须得更新距离了…由于新加入的结点可能发出边使得原来源点到某些结点的距离更小,也就是我们的源点变大了,边也变多了,所以我们的最短距离集合的值也必须变化了…
该算法一直循环nN-1次,直至所有的点都加入源点顶点集合…

发表于 分类于 ， 阅读次数： Valine：
本文字数： 2.4k 阅读时长 ≈ 2 分钟

链接: http://poj.grids.cn/practice/2814

这个题目可以枚举或者直接暴力。但是,这之前必须弄明白答案的解空间。。。也就是解可能的情况。。。很简单,一共有9种移动方案。也很了然的知道对于某种方案使用N次的效果等同于N%4的效果,也就是说某种方案只可能使用0,1,2,3次。。。一共有9种方案,那么一共就只有4^9种可能的解。。。这么小的解空间,无论用什么方法都不会超时了。。。暴力可以才用9重循环,或者深搜,当时觉得写9重循环是件很糗的事情,就果断深搜了。。。
如果这题才用枚举的方法的话,思考方式还是那样先确定假设解的部分情况,通过已经知道的规则确定解的其它情况,然后求出这个解,判断这个解是否满足题目要求。。。比如,我们可以枚举1,2,3号方案的情况,根据规则确定其它方案的使用情况,求出所有方案的使用情况后,判断假设的解是否满足要求就可以了…

我才用的是dfs+剪枝,这个题目其实题意或者说答案有误,因为答案是搜索找到第一个解,而不是所谓的最短序列的解,当然如果数据使得2者都是一样的话,那么题意就无误了…我的代码是假设找到的第一个就是最短序列的,这种情况下才能使用剪枝,因为找到一个解后就不需要继续找了…

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h>
int nMinTimes;
int nPath[40];
bool bFind = false;
char* szMoves[10] =
{
    NULL,
    "ABDE",
    "ABC",
    "BCEF",
    "ADG",
    "BDEFH",
    "CFI",
    "DEGH",
    "GHI",
    "EFHI"
};
bool IsPosOK(int* nPos)
{
    for (int i = 0; i < 9; ++i) { if (nPos[i]) { return false; } } return true; } void Move(int nChoose, int nTimes, int* nPos) { if (nTimes > 0)
    {
        char* pszStr = szMoves[nChoose];
        while (*pszStr)
        {
            nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] + nTimes) % 4;
            ++pszStr;
        }
    }
}
void MoveBack(int nChoose, int nTimes, int* nPos)
{
    if (nTimes > 0)
    {
        char* pszStr = szMoves[nChoose];
        while (*pszStr)
        {
            nPos[*pszStr - 'A'] = (nPos[*pszStr - 'A'] - nTimes + 4) % 4;
            ++pszStr;
        }
    }
}
void Cal(int nChoose, int* nPos, int* nUsed, int nUsedTimes)
{
    if (nChoose == 10)
    {
        if (IsPosOK(nPos) && !bFind)
        {
            nMinTimes = nUsedTimes;
            for (int i = 0; i < nMinTimes; ++i)
            {
                nPath[i] = nUsed[i];
            }
            bFind = true;
        }
        return;
    }
    for (int i = 0; i <= 3; ++i)
    {
        Move(nChoose, i, nPos);
        for (int j = 0; j < i; ++j)//放入i次的nChoose
        {
            nUsed[nUsedTimes + j] = nChoose;
        }
        if (!bFind)
        {
            Cal(nChoose + 1, nPos, nUsed, nUsedTimes + i);
        }
        MoveBack(nChoose, i, nPos);
    }
}
int main()
{
    int nPos[9];
    int nUsed[40];
    for (int i = 0; i < 9; ++i)
    {
        scanf("%d", &nPos[i]);
    }
    Cal(1, nPos, nUsed, 0);
    for (int i = 0; i < nMinTimes; ++i)
    {
        printf("%d", nPath[i]);
        if (i != nMinTimes - 1)
        {
            putchar(' ');
        }
        else
        {
            putchar('\n');
        }
    }

    return 0;
}

这道题其实我wa了近10次,原因就是Move和MoveBack写错了,没有移动nTimes次,而前面一直写成了1,昨晚wa得实在无语了…今天晚上检查才突然发现的…
这半个多月做了60道题了,都没有改动这低级的bug习惯…实在无语…递归,回溯,剪枝都写上了…唉…实在无语…还不如直接9重循环,多省心…真不该歧视某种方法的…

发表于 分类于 ， 阅读次数： Valine：
本文字数： 1.6k 阅读时长 ≈ 1 分钟

链接：http://poj.grids.cn/practice/1183/

方法1:
本题很容易推断出 ,a = (b * c - 1) / (b + c), 由于需要求(b+c)的最小值,根据高中的函数思想,如果(b+c)能够转换为关于b或者c的函数就好办了,刚好这里已经有个b和c的关系式子了,可以推导出(b+c) = (c^2+1)/(c-a),这个时候只需要求f(c)的最小值,但是c必须取整数,对这个函数可以求导,也可以进行变形,变形后可以得到f(c) = (c-a) + 2 a + (a^2+1)/(c-a)。
令x=c-a,那么可以得到(b+c)=f(x)=x + 2 a+(a^2+1)/x, 其中x必须是整数,到现在为止就是一个用程序模拟高中时候学过的双曲线函数的求最值问题了,我们知道该函数的极值点是sqrt(a^2+1),但是由于x必须是整数,
我们必须从极值开始往下和往上找到一个最小值,然后取2者中的最小值…这样这个题就解出来了…

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <iostream>
#include <math.h>
//b + c = (c^2 + 1) / (c - a) = (c-a) + (2 * a) + (a^2 + 1) / (c -a)
//令c-a = t, f(t) = t + 2*a + (a^2+1)/ t
//因为f(t)在sqrt(a^2+1)时取最小值,但是由于t只能取整数,
//所以,必须从极值点往下和往上寻找最小的值,然后取2者中最小的
int main()
{
    long long a;
    while (std::cin >> a)
    {
        long long nTemp = a * a + 1;
        long long nDown =  sqrt(nTemp);
        long long nUp = nDown;
        long long one, two;

        while (nTemp % nDown )
        {
            nDown--;
        }
        one = 2 * a + nTemp / nDown + nDown;

        while (nTemp % nUp )
        {
            nUp++;
        }
        two = 2 * a + nTemp / nUp + nUp;

        std::cout << (one < two ? one : two) << std::endl;
    }
    return 0;
}

方法2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <iostream>
#include <math.h>

//a = (b*c-1)/(b+c)
//令b = a + m, c = a + n, c >= b
//-> a*(2*a+m+n) = (a+m)*(a+n)-1
//m*n = a^2 + 1  (n>=m)
//所以,求出a^2+1所有因子对,取其中m+n最小的即可
int main()
{
    long long a;
    while (std::cin >> a)
    {
        long long m, n;
        long long nTemp = a * a + 1;
        long long nMax = sqrt(nTemp);
        long long nRes = 1 + nTemp;
        for (m = 2; m <= nMax; ++m)
        {
            if (nTemp % m == 0)
            {
                n = nTemp / m;
                if (m + n < nRes)
                {
                    nRes = m + n;
                }
            }
        }

        std::cout << 2 * a + nRes << std::endl;
    }
    return 0;
}