求解uva 10163 一道DP题ACM高手来 - 数据结构与算法

第 11 楼

得分:0

版主太客气了，每次都给评分

不过，楼上的代码仍然过不了一些特殊的数据。
比如：
10 6
9 9 5 9 3 3
10 6
3 1 7 8 10 7
8 6
1 1 10 4 7 5
-----------------
3 30
3 35
2 17

收到的鲜花

寒风中的细雨于 2011-06-09 23:33 送鲜花 10朵附言：这个测试很有用。。。不然很难找出来这样子 ...

第 12 楼

得分:0

谁有兴趣可以修改下面的代码
主要是求最高安全线

程序代码：

#include <iostream>
using namespace std;

const size_t MAX_SIZE = 30;

struct Pi
{
    unsigned short m_Value;
    unsigned short m_Sum;

};

struct Pi piArray[MAX_SIZE];
size_t nValue;//表示仓库的数量
size_t mValue;//表示人的个数

bool getConsoleInputs()
{//获取终端的输入信息
    size_t i=0;

    cin >> nValue >> mValue;
    while (i!=mValue && cin>>piArray[i].m_Value)
    {
        piArray[i].m_Sum = 0;//初始化最初分配到的仓库数量为零
        ++i;
    }

    return (nValue && mValue);
}

/*

 *找出一定范围内[0, suffix]平均Pi值最大的下标值

 */
size_t findMaxAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/piArray[i].m_Sum) >
            (piArray[k].m_Value/piArray[k].m_Sum))
        {
            k = i;
        }
    }

    return k;
}

/*

 *找出一定范围内[0, suffix]平均Pi值最小的下标值

 */
size_t findMinAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/piArray[i].m_Sum) <
            (piArray[k].m_Value/piArray[k].m_Sum))
        {
            k = i;
        }
    }

    return k;
}

/*

 *调整每个人所分配到的仓库数量

 *根据仓库的数量(nValue) 人的个数(mValue)以及Pi

 *进行人员的合理分配使得到最高的安全线

 *返回总的看守仓库的人数

 */
size_t adjustm_Sum()
{
    size_t i, j, suffix=0;
   
    piArray[0].m_Sum = 1;//开始的状态为分配一个仓库数量
    for (i=1; i<nValue; ++i)
    {
        if (i < mValue)
        {
            j = findMaxAvgPiIndex(suffix);
            if (piArray[j].m_Value/(piArray[j].m_Sum+1) >= piArray[suffix+1].m_Value)
            {
                ++(piArray[j].m_Sum);
            }
            else
            {
                ++(piArray[suffix+1].m_Sum);
                ++suffix;//添加新的元素
            }
        }
        else
        {
            j = findMaxAvgPiIndex(suffix);
            ++(piArray[j].m_Sum);
        }
    }

    return suffix+1;
}

//piArray数组降序排序
void sort()
{//采用选择法排序
    size_t i, j, k;
    unsigned short temp;

    for (i=0; i<mValue-1; ++i)
    {
        k = i;
        for (j=i+1; j<mValue; ++j)
        {
            if (piArray[j].m_Value > piArray[k].m_Value)
            {
                k = j;
            }
        }
        if (k != i)
        {
            temp = piArray[k].m_Value;
            piArray[k].m_Value = piArray[i].m_Value;
            piArray[i].m_Value = temp;
        }
    }
}
/*

 *输出最高的安全线

 */
void showHighL()
{
    size_t suffix = adjustm_Sum();
    size_t i = findMinAvgPiIndex(suffix-1);
    printf("%d \n\n", piArray[i].m_Value/piArray[i].m_Sum);
}

void function()
{
    while (getConsoleInputs())
    {
        sort();
        showHighL();
    }
}

int main(void)
{
    function();

    return 0;
}

这是上面的用例

第 13 楼

得分:0

输出为神马只有一个？

第 14 楼

得分:0

http://
上这个网输入题号10163，点击题目栏，在它弹出框的左框（input框）输入你想要测的数据，点击上传，就可以得到标准答案。
有个弊端就是如果想换个输入数据，更换后要点击两次上传。

第 15 楼

得分:0

程序代码：

#include <iostream>
using namespace std;

const size_t MAX_SIZE = 30;

struct Pi
{
    unsigned short m_Value;
    unsigned short m_Sum;

};

struct Pi piArray[MAX_SIZE];
size_t nValue;//表示仓库的数量
size_t mValue;//表示人的个数

bool getConsoleInputs()
{//获取终端的输入信息
    size_t i=0;

    cin >> nValue >> mValue;
    while (i!=mValue && cin>>piArray[i].m_Value)
    {
        piArray[i].m_Sum = 0;//初始化最初分配到的仓库数量为零
        ++i;
    }

    return (nValue && mValue);
}

/*
*找出一定范围内[0, suffix]平均Pi值最大的下标值
*/
size_t findMaxAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/piArray[i].m_Sum) >
            (piArray[k].m_Value/piArray[k].m_Sum))
        {
            k = i;
        }
    }

    return k;
}

/*
*找出一定范围内[0, suffix]平均Pi值最小的下标值
*/
size_t findMinAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/piArray[i].m_Sum) <
            (piArray[k].m_Value/piArray[k].m_Sum))
        {
            k = i;
        }
    }

    return k;
}

/*
*找出一定范围内[0, suffix]平均Pi在m_Sum加上1的情况下值最大的下标值
*/
size_t findInreMaxAvgPiIndex(size_t suffix)
{
    size_t i=0, k=0;

    for (; i<=suffix; ++i)
    {
        if ((piArray[i].m_Value/(piArray[i].m_Sum+1)) >
            (piArray[k].m_Value/(piArray[k].m_Sum+1)))
        {
            k = i;
        }
    }

    return k;
}

/*
*调整每个人所分配到的仓库数量
*根据仓库的数量(nValue) 人的个数(mValue)以及Pi
*进行人员的合理分配使得到最高的安全线
*返回总的看守仓库的人数
*/
size_t adjustm_Sum()
{
    size_t i, j, k, suffix=0;
  
    piArray[0].m_Sum = 1;//开始的状态为分配一个仓库数量
    for (i=1; i<nValue; ++i)
    {
        if (suffix < mValue)
        {
            j = findMaxAvgPiIndex(suffix);
            k = findInreMaxAvgPiIndex(suffix);
            if (piArray[k].m_Value/(piArray[k].m_Sum+1) >= piArray[suffix+1].m_Value)
            {
                ++(piArray[k].m_Sum);
            }
            else if (piArray[j].m_Value/(piArray[j].m_Sum+1) >= piArray[suffix+1].m_Value)
            {
                ++(piArray[j].m_Sum);
            }
            else
            {
                ++(piArray[suffix+1].m_Sum);
                ++suffix;//添加新的元素
            }
        }
        else
        {
            j = findMaxAvgPiIndex(suffix);
            ++(piArray[j].m_Sum);
        }
    }

    return suffix+1;
}

//piArray数组降序排序
void sort()
{//采用选择法排序
    size_t i, j, k;
    unsigned short temp;

    for (i=0; i<mValue-1; ++i)
    {
        k = i;
        for (j=i+1; j<mValue; ++j)
        {
            if (piArray[j].m_Value > piArray[k].m_Value)
            {
                k = j;
            }
        }
        if (k != i)
        {
            temp = piArray[k].m_Value;
            piArray[k].m_Value = piArray[i].m_Value;
            piArray[i].m_Value = temp;
        }
    }
}
/*
*输出最高的安全线
*/
void showHighL()
{
    size_t suffix = adjustm_Sum();
    size_t i = findMinAvgPiIndex(suffix-1);
    printf("%d \n\n", piArray[i].m_Value/piArray[i].m_Sum);
}

void function()
{
    while (getConsoleInputs())
    {
        sort();
        showHighL();
    }
}

int main(void)
{
    function();

    return 0;
}

第 16 楼

得分:0

回复 13楼 brian1994

整个问题可以分解成两部分来做
1、求最高安全线    2、求最低工资
上面的代码  就是求最高的安全线的

求最低工资是需要第一步求得的最高安全线：
基本思路是 m_Value对最高安全线求余最小在基本条件是m_value>=最高安全线  结束条件为求得的仓库数量刚好=nValue