P8794 [蓝桥杯 2022 国 A] 环境治理 题解

· · 题解

1. 编程思路。

用二分法来求最少要经过多少天后 P 指标可以满足要求。

初始定义治理需要的最少天数 left=0，治理需要的最多天数可设为每个城市治理十万天，置 right=100000\times n，取 left 和 right 的中值 mid，计算经过 mid 天治理后的 P 指标值。若 P 指标值满足要求，说明还有减少治理天数的希望，置 right=mid-1；若 P 指标值不满足要求，说明治理的天数不够，需要增加治理天数，置 left=mid。

在计算治理 mid 天后的 P 指标值时，采用 Floyed 算法求任意两个城市间的最短距离（最小的灰尘度的值）。

2. 源程序。

#include <stdio.h>
#include <string.h>
int d[105][105];
int limit[105][105];
int n;
int min(int a,int b)
{
    return a<b?a:b;
}
int calc(int day)          // 计算经过day 天治理后的P指标值
{
    int tmp[105][105];     // 用于治理的辅助数组
    int i,j,k;
    for (i =0; i<n; i++)
        for (j =0; j<n; j++)
            tmp[i][j]=d[i][j];
    for (i =0; i<n; i++)
    {
        int val = day/n+(day%n>=i+1?1:0);
        for (j =0 ; j<n; j++)
        {
            tmp[i][j]-=val;
            if (tmp[i][j]<limit[i][j]) tmp[i][j]=limit[i][j];
            tmp[j][i]-=val;
            if (tmp[j][i]<limit[j][i]) tmp[j][i]=limit[j][i];
        }
    }
    for (k =0 ; k<n; k++)        // floyed 算法求最短路径
        for (i =0 ; i<n; i++)
            for (j =0 ; j<n; j++)
                tmp[i][j]=min(tmp[i][j],tmp[i][k]+tmp[k][j]);
    int res =0 ;
    for (i =0; i<n; i++)     // 计算治理后的P指标值
        for (j =0; j<n; j++)
            res+=tmp[i][j];
    return res ;
}
int main()
{
    int q;
    scanf("%d %d",&n,&q);
    int i,j;
    for (i =0; i<n; i++)
        for (j =0 ; j<n; j++)
            scanf("%d",&d[i][j]);
    for (i =0; i<n; i++)
        for (j =0 ; j<n; j++)
            scanf("%d",&limit[i][j]);
    int  left =0,right= 100000*n,ans =-1;
    while (left<=right)
    {
        int mid = (left+right)/2;
        if (calc(mid)<=q)
        {
            right= mid -1;
            ans = mid;
        }
        else
            left=mid+1;
    }
    printf("%d\n",ans);
    return 0;
}