题目描述

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

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

思路

本题我们来讲解 数组 上常用的解题技巧：前缀和，极其适用于计算区间和。

暴力解法

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    for (int i = 0; i < n; i++) cin >> vec[i];
    while (cin >> a >> b) {
        int sum = 0;
        // 累加区间 a 到 b 的和
        for (int i = a; i <= b; i++) sum += vec[i];
        cout << sum << endl;
    }
} 

思考

为什么输入区间要是0 1，而不能是01，哪里体现了要求输入空格？

在这段代码中，输入区间时需要输入 0 1 而不是 01，是因为 C++ 的输入流 cin 通过空格分隔不同的输入项。如果输入 01：代码会尝试将 01 作为一个整数赋值给 a（例如解析为 1）。

由于没有第二个输入项，b 的值未被正确初始化，导致后续的 vec[i] 访问可能越界（如 a=1 但数组长度仅为 n），引发未定义行为（如程序崩溃或错误输出）。

int main()
{
	using namespace std;
	int n, a, b;
	cin >> n;
	vector<int> vec(n);
	vector<int> p(n);
	int presume = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> vec[i];
		presume += vec[i];
		p[i] = presume;
	}

	while (cin >> a >> b)
	{
		int sum;
		if (a == 0) sum = p[b];
		else sum = p[b] - p[a - 1];
		cout << sum << endl;
	}
}

C++ 代码 面对大量数据 读取 输出操作，最好用scanf 和 printf，耗时会小很多：

#include <iostream>
#include <vector>
using namespace std;
int main() {
    int n, a, b;
    cin >> n;
    vector<int> vec(n);
    vector<int> p(n);
    int presum = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &vec[i]);
        presum += vec[i];
        p[i] = presum;
    }

    while (~scanf("%d%d", &a, &b)) {
        int sum;
        if (a == 0) sum = p[b];
        else sum = p[b] - p[a - 1];
        printf("%d\n", sum);
    }
}

其中

• scanf(“%d”, &vec[i]);
• 功能：从标准输入读取一个整数，存储到 vec[i] 中。
• 格式字符串 %d：表示读取一个十进制整数。
• 参数 &vec[i]：传递变量地址，确保数据写入正确内存位置。

• while (~scanf(“%d%d”, &a, &b))；
• 功能：持续读取两个整数 a 和 b，直到输入结束（如文件结尾或错误）。
• ~scanf(...) 等价于 !EOF，循环继续执行。

44. 开发商购买土地（第二个解法看不懂，count要count出去count）

【题目描述】

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

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

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

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

注意：区块不可再分。

思路

本题也可以使用 前缀和的思路来求解，先将 行方向，和 列方向的和求出来，这样可以方便知道 划分的两个区间的和。

#include<iostream>
#include<vector>
#include<climits>

using namespace std;
int main()
{
	int n, m;
	cin >> n >> m;
	int sum = 0;
	vector<vector<int>> vec(n, vector<int>(m, 0));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> vec[i][j];
			sum += vec[i][j];
		}
	}
	//统计横向
	vector<int> horizontal(n, 0);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			horizontal[i] += vec[i][j];
		}
	}
	//统计纵向
	vector<int> vertical(m, 0);
	for (int j = 0; j < m; j++)
	{
		for (int i = 0; i < n; i++)
		{
			vertical[j] += vec[i][j];
		}
	}
	int result = INT_MAX;
	int horizontalCut = 0;
	for (int i = 0; i < n; i++)
	{
		horizontalCut += horizontal[i];
		result = min(result, abs(sum - horizontalCut - horizontalCut)); //差值计算，
	}
	int verticalCut = 0;
	for (int j = 0; j < m; j++)
	{
		verticalCut += vertical[j];
		result = min(result, abs(sum - verticalCut - verticalCut));
	}
	cout << result << endl;
}

• 差值的数学推导：
  若切割后前一部分和为 A，后一部分和为 sum - A，则差值为：∣A−(sum−A)∣=∣sum−2A∣∣A−(sum−A)∣=∣sum−2A∣代码通过累加行或列的和，逐步计算每个切割点的 A，并更新最小差值。

vector<vector<int>> vec(n, vector<int>(m, 0)); 这行代码的作用是创建一个二维动态数组（矩阵），具体含义如下：

• 类型：vector<vector<int>> 表示这是一个「向量的向量」，即二维向量。
• 变量名：vec 是该二维向量的名称。
• 初始化参数：(n, vector<int>(m, 0))
• 总共有 n 行，每行 m 列，所有元素初始值为 0。

vector<int> horizontal(n, 0); 这行代码的作用是创建一个名为 horizontal 的 一维动态数组（容器），其初始化的具体含义如下：

• 类型：vector<int> 表示这是一个存储 int 类型元素的一维动态数组。
• 变量名：horizontal 是数组的名称。
• 初始化参数：(n, 0)

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
int main () {
    int n, m;
    cin >> n >> m;
    int sum = 0;
    vector<vector<int>> vec(n, vector<int>(m, 0)) ;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> vec[i][j];
            sum += vec[i][j];
        }
    }

    int result = INT_MAX;
    int count = 0; // 统计遍历过的行
    for (int i = 0; i < n; i++) {
        for (int j = 0 ; j < m; j++) {
            count += vec[i][j];
            // 遍历到行末尾时候开始统计
            if (j == m - 1) result = min (result, abs(sum - count - count));

        }
    }

    count = 0; // 统计遍历过的列
    for (int j = 0; j < m; j++) {
        for (int i = 0 ; i < n; i++) {
            count += vec[i][j];
            // 遍历到列末尾的时候开始统计
            if (i == n - 1) result = min (result, abs(sum - count - count));
        }
    }
    cout << result << endl;
}