View Code of Problem 3565

#include <stdio.h>

 

int n;//湖的个数

int h;//可用时间

int fi[30];//最初钓鱼量

int di[30];//单位时间鱼的减少量

int cfi[30];//对 fi 数组的保存

int ti[30];//ti[i] 表示从第 i 个湖到第 i+1 湖的时间

 

struct LAKENODE

{

    int num[30];

    int max;

}lake[30];//用结构体数组保存可能解

 

int GetMax(int p[], int i, int j)//返回数组 p 中最大数的编号

{

    int cmax = p[i], loc = i;// loc :最大数的位置

    for (int m = i + 1; m <= j; m++)

    {

        if (cmax < p[m])

        {

            cmax = p[m];

            loc = m;

        }

    }

    return loc;

}

 

void GetFish()

{

    int i, j;

    int T = h * 60, t, CT;

    for(i = 1; i <= n; i++)//结构体数组初始化，全部置零

    {

        lake[i].max = 0;

        for(int j = 1; j <= n; j++)

        {

            lake[i].num[j] = 0;

        }

    }

    for (i = 1;i <= n; i++)//枚举结束湖的位置,从第一个湖到第n个湖

    {

        CT = T;

        t = 0;

        for (j = 1; j <= i; j++)

        {

            cfi[j] = fi[j];//将fi数组的值拷贝到cfi数组中

            CT = (j < i) ? CT - ti[j] * 5 : CT;//计算除去走路时间后的剩余时间

        }

        while (t < CT)

        {

            int k = GetMax(cfi, 1, i);//找到钓鱼量最多的湖的编号

            lake[i].max += cfi[k];//钓鱼总量增加在k湖一个单位时间钓到的鱼

            lake[i].num[k] += 5;//停在k湖的时间增加一个单位时间

            cfi[k] >= di[k] ? cfi[k] -= di[k] : cfi[k] = 0;//修改第k个湖在下一个时间单位中所能钓到的鱼

            t += 5;//时间增加一个单位时间

        }

    }

    for (i = 1; i <= n; i++)//将最大值拷贝到cfi数组中，用于查询真正最大值

    {

        cfi[i] = lake[i].max;

    }

    int la = GetMax(cfi, 1, n);//la：最优解下标

    for (i = 1; i <= n; i++)

    {

        (i != n) ? printf("%d, ", lake[la].num[i]) : printf("%d", lake[la].num[i]);

    }

    printf("\nNumber of fish expected: %d\n\n", lake[la].max);

}

 

int main()

{

    int i;

    while (scanf("%d", &n) && n)

    {

        scanf("%d", &h);

        for (i = 1; i <= n; i++)

        {

            scanf("%d", &fi[i]);

        }

        for (i = 1; i <= n; i++)

        {

            scanf("%d", &di[i]);

        }

        for (i = 1; i < n; i++)

        {

            scanf("%d", &ti[i]);

        }

        GetFish();

    }

    return 0;

}