蓝桥杯备赛-基础训练（一）数组 day13

区间和

题目描述

给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。

输入描述

第一行输入为整数数组 Array 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间，直至文件结束。

输出描述

输出每个指定区间内元素的总和。

输入示例

5
1
2
3
4
5
0 1
1 3

输出示例

3
9

数据范围：

0 < n <= 100000

思路：

和卡哥是一样的，

我一开始真的是以为直接用暴力解法就可以解决（给一个区间，然后把这个区间的和都累加一遍不就得了）

但是后来发现，根本不是这样的，这样的撰写是会超时的

我们可以使用前缀和的方式来撰写代码：

如果，我们想统计，在vec数组上 下标 2 到下标 5 之间的累加和，那是不是就用 p[5] - p[1] 就可以了。

为什么呢？

p[1] = vec[0] + vec[1];

p[5] = vec[0] + vec[1] + vec[2] + vec[3] + vec[4] + vec[5];

p[5] - p[1] = vec[2] + vec[3] + vec[4] + vec[5];

这样只要执行一次循环就可以了，然后我们用一次减就ok啦

代码：

# 区间和
# 读取数组长度
n = int(input("请输入你要输入几个数字："))
arr = []
# 读取数组元素
for i in range(0,n):
    num = int(input( ))
    arr.append(num)

arr_sum = [0]*n
k = 0

for i in range(n):
    k = k+arr[i]
    arr_sum[i]=k

print(arr_sum)


arr_1 = [0]*2
s_1 = input("输入你想知道的区间，以空格为分隔：")
arr_1 = list(map(int,s_1.split( )))
jiange = arr_sum[arr_1[1]-1]-arr_sum[arr_1[0]-1]
print(jiange)

开发商购买土地

题目描述：

在一个城市区域内，被划分成了n * m个连续的区块，每个区块都拥有不同的权值，代表着其土地价值。目前，有两家开发公司，A 公司和 B 公司，希望购买这个城市区域的土地。

现在，需要将这个城市区域的所有区块分配给 A 公司和 B 公司。

然而，由于城市规划的限制，只允许将区域按横向或纵向划分成两个子区域，而且每个子区域都必须包含一个或多个区块。

为了确保公平竞争，你需要找到一种分配方式，使得 A 公司和 B 公司各自的子区域内的土地总价值之差最小。

注意：区块不可再分。

【输入描述】

第一行输入两个正整数，代表 n 和 m。

接下来的 n 行，每行输出 m 个正整数。

输出描述

请输出一个整数，代表两个子区域内土地总价值之间的最小差距。

【输入示例】

3 3 1 2 3 2 1 3 1 2 3

【输出示例】

0

【提示信息】

如果将区域按照如下方式划分：

1 2 | 3 2 1 | 3 1 2 | 3

两个子区域内土地总价值之间的最小差距可以达到 0。

【数据范围】：

• 1 <= n, m <= 100；
• n 和 m 不同时为 1。

思路：

看到本题，大家如果想暴力求解，应该是 n^3 的时间复杂度，

一个 for 枚举分割线， 嵌套 两个for 去累加区间里的和。

但是这个的循环要很多很多，而且其实我感觉不容易写出来

但是如果结合我们的区间和这里的前缀来看，其实是很容易的，而且循环的次数就不会那么多了

代码：

# 开发商购买土地
def find_mini(a:int,b:int)->int:
    if a>b:
        return b
    else:
        return a

hang_lie = [0]*2
s = input("请输入你要几行几列，以空格为分隔：")
hang_lie = list(map(int,s.split()))
num=[]#初始化列表
for i in range(hang_lie[0]):
    row = list(map(int,input().split()))
    num.append(row)
print(num)
hang = hang_lie[0]
lie = hang_lie[1]
hang_list = [0]*hang
lie_list = [0]*lie
# 以行为标准循环后得到每一行的值
i = 0
j = 0
for i in range(hang):
    sum = 0
    for j in range(lie):
        sum = sum+num[i][j]
    hang_list[i] = sum
# 以列表为标准循环后得到每一列的值
i = 0
j = 0
for j in range(lie):
    sum = 0
    for i in range(hang):
        sum = sum+num[i][j]
    lie_list[j] = sum

print(hang_list)
print(lie_list)


min = 1000
for i in range(hang):
    for j in range(i+1,hang):
        min = find_mini(min,hang_list[j]-hang_list[i])
for i in range(lie):
    for j in range(i+1,lie):
        min = find_mini(min,lie_list[j]-lie_list[i])
print(min)