G20|A2.数方格题解——找规律法

G20|A2.数方格题解——找规律法

——————看之前先点个赞吧，谢谢！——————

较详细题解

大概思路:

在一个长方形中，最大正方形的边长=长、宽最短的一个
接着数一数，发现规律：

正方形边长	个数
1	m * n
2	( m - 1 ) * ( n - 1 )
3	( m - 2 ) * ( n - 2 )
......	......
min(n,m)	1 * ( max ( n , m )-( min ( n , m ) - 1 ) )

按规律在代码中用计数器数正方形

综上，写出代码：

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

int main(){
    //初始化长,宽,计数器,要用long long
    long long n,m,sum = 0;
    //输入长和宽
    cin >> n >> m;
    //主体部分
    for(int i = n,j = m;min(i,j) > 0;i--,j--)//规律:范围缩小
        sum += i*j;//计数器增加
    //输出结果
    cout << sum;
    return 0;
}

时间复杂度是

O(min(n,m))

//解析：主体部分一层循环循环min(n,m)次