题解：CF2033B Sakurako and Water

lailai0916 · 2024-10-25 10:02:18 · 题解

解题思路

每个子矩阵的主对角线操作是相互独立的。

因此可以单独处理每条对角线。我们首先考虑每条对角线，找到该对角线上的最小值，然后将其提升到非负数，这样整条对角线上的所有值都变为非负。

将每个 a_{i,j} 统计到其所在的对角线编号 i-j+n。

对于每条对角线，如果最小值 b_i 为负数，我们需要执行 -b_i 次操作将其提升到非负值。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
const int N=505;
int a[N][N],b[N<<1];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=(n<<1)-1;i++)b[i]=inf;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>a[i][j];
                b[i-j+n]=min(b[i-j+n],a[i][j]);
            }
        }
        int ans=0;
        for(int i=1;i<=(n<<1)-1;i++)
        {
            if(b[i]<0)ans-=b[i];
        }
        cout<<ans<<'\n';
    }
    return 0;
}