小美的蛋糕切割

#include <iostream>
#include <vector>

using namespace std;


long long fun (vector<vector<int>>& arr, int n, int m) {
    // 求二维矩阵前缀和 之后的每一刀相当于求每个区间的美味度
    vector<vector<long long>> arr_b(n + 1, vector<long long>(m + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            arr_b[i][j] = arr_b[i - 1][j] + arr_b[i][j - 1] - arr_b[i - 1][j - 1] + arr[i][j];
        }
    }

    long long s1, s2;
    long long min_result = arr_b[n][m];
    // 横切
    for (int i = 1; i < n; i++) {
        s1 = arr_b[i][m];
        s2 = arr_b[n][m] - s1;
        if (abs(s1 - s2) < min_result) min_result = abs(s1 - s2);
    }

    // 竖切
    for (int j = 1; j < m; j++) {
        s1 = arr_b[n][j];
        s2 = arr_b[n][m] - s1;
        if (abs(s1 - s2) < min_result) min_result = abs(s1 - s2);
    }

    return min_result;
}

int main () {

    int n, m;

    scanf("%d %d", &n, &m);

    vector<vector<int>> arr(n + 1, vector<int>(m + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &arr[i][j]);
        }
    }

    long long result = fun(arr, n, m);

    printf("%lld", result);

    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=in.nextInt();
        long[]row=new long[n];
        int m=in.nextInt();
        long[]col=new long[m];
        int[][]matrix=new int[n][m];
        for (int i = 0; i < n; i++) {
            if (i>0) row[i]=row[i-1];
            for (int j = 0; j < m; j++) {
                matrix[i][j]=in.nextInt();
                row[i]+=matrix[i][j];
            }
        }
        long sum=row[n-1];
        for (int i = 0; i < m; i++) {
            if (i>0) col[i]=col[i-1];
            for (int j = 0; j < n; j++) {
                col[i]+=matrix[j][i];
            }
        }
        long ans=Long.MAX_VALUE;
        for (long a:row){
            ans=Math.min(ans,Math.abs(sum-a*2));
        }
        for (long a:col){
            ans=Math.min(ans,Math.abs(sum-a*2));
        }
        System.out.println(ans);
    }
}

h, w = [int(n) for n in input().split()]
m = []
for i in range(h):
    m.append([int(n) for n in input().split()])

h_sum = [sum([m_[i] for m_ in m]) for i in range(w)]
w_sum = [sum(m[i]) for i in range(h)]
max = sum(w_sum)

for i in range(1, w):
    part1_sum = sum(h_sum[:i])
    part2_sum = sum(h_sum[i:])
    sub = abs(part1_sum - part2_sum)
    if sub < max:
        max = sub
    
for i in range(1, h):
    part1_sum = sum(w_sum[:i])
    part2_sum = sum(w_sum[i:])
    sub = abs(part1_sum - part2_sum)
    if sub < max:
        max = sub

print(max)

一开始想用golang结果超时，同样的方法放到C++就通过了……还得是C++

用C++需要注意：输入的数据用int确实没问题，但求和的时候如果还用int的话会溢出导致WA，建议除了代表地址的n,m,i,j之外无脑long long。

#include <iostream>
#include <algorithm>

long long matrix[1000][1000];
long long sumByLine[1000];
long long sumByColumn[1000];
long long prefixByLine[1000];
long long prefixByColumn[1000];
long long distanceByLine[1000];
long long distanceByColumn[1000];

int main(int argc, char* argv[]){
    std::cin.tie(nullptr); std::cout.tie(nullptr);std::ios::sync_with_stdio(false);
    int n, m;
    std::cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            std::cin >> matrix[i][j];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            sumByLine[i] += matrix[i][j];
            sumByColumn[j] += matrix[i][j];
        }
    }
    prefixByLine[0] = sumByLine[0];
    prefixByColumn[0] = sumByColumn[0];
    for (int i = 1; i < n; i++) {
        prefixByLine[i] = prefixByLine[i-1] + sumByLine[i];
    }
    for (int i = 1; i < m; i++) {
        prefixByColumn[i] = prefixByColumn[i-1] + sumByColumn[i];
    }

    for (int i = 0; i < n; i++) {
        distanceByLine[i] = std::abs(prefixByLine[n-1] - 2*prefixByLine[i]);
    }
    for (int i = 0; i < m; i++) {
        distanceByColumn[i] = std::abs(prefixByColumn[m-1] - 2*prefixByColumn[i]);
    }
    long long minDistanceByLine = *(std::min_element(distanceByLine, distanceByLine+n));
    long long minDistanceByColumn = *(std::min_element(distanceByColumn, distanceByColumn+m));
    std::cout << std::min(minDistanceByLine, minDistanceByColumn);
    return 0;
}

import java.util.Scanner;

import static java.lang.Math.abs;

public class Main {
    public static  void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int x=sc.nextInt();
        int y=sc.nextInt();
        long[][] arr = new long[x][y];
        long sum=0;
        long []line=new long[x];
        long []row=new long[y];
       
        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                arr[i][j]=sc.nextInt();
                sum+=arr[i][j];
            }
        }
        for (int a = 0; a < x; a++) {
            line[a]=0;
            for (int b = 0; b < y; b++) {
                line[a]+=arr[a][b];
            }


        }
        for (int c = 0; c < y; c++) {
            row[c] = 0;
            for (int d = 0; d < x; d++) {
                row[c] += arr[d][c];
            }
        }
        long lines=line[0];
        long rows=row[0];
        long linemin=abs(sum-2*line[0]);
        long rowmin=abs(sum-2*row[0]);
        for (int p = 1; p < x-1; p++) {
            lines+=line[p];
            if(abs(sum-2*lines)<linemin)linemin=abs(sum-2*lines);
        }
        for(int q=1;q<y-1;q++){
            rows+=row[q];
            if(abs(sum-2*rows)<rowmin)rowmin=abs(sum-2*rows);
        }
        System.out.println(linemin<=rowmin?linemin:rowmin);
    }
}

import java.util.Scanner;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        long[][] w = new long[n][m];
        // 注意 hasNext 和 hasNextLine 的区别
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < m; j++)
            {
                w[i][j] = in.nextLong();
                if(i == 0 && j == 0) continue;
                if(i == 0) {w[i][j] += w[i][j - 1];continue;}
                if(j == 0) {w[i][j] += w[i - 1][j];continue;}
                w[i][j] += w[i - 1][j] + w[i][j - 1] - w[i - 1][j - 1];
            }
        }
        long s1 = 0;
        long s2 = 0;
        long res = Long.MAX_VALUE;
        for(int i = 0; i < n ; i++)
        {
            s1 = w[i][m-1];
            s2 = w[n-1][m-1] - s1;
            res =Math.min(res,Math.abs(s1-s2));
        }
        for(int i = 0; i < m ; i++)
        {
            s1 = w[n-1][i];
            s2 = w[n-1][m-1] - s1;
            res =Math.min(res,Math.abs(s1-s2));
        }
        System.out.println(res);
        return ;
    }
}

#include <stdio.h>


long long Min_arr(long long arr[], int n)
{

    long long MID = arr[n - 1] / 2;
    int left = 0;
    int right = n - 2;
    int mid = 0;

    long long min_arr = 0;
    int i=0;
      while(arr[i]<MID)
      {
        i++;
      }
   if(i==0)
   {
    min_arr=2*arr[i]-arr[n-1];
   }
   else{
    min_arr=(arr[n-1]-2*arr[i-1]<2*arr[i]-arr[n-1]?arr[n-1]-2*arr[i-1]:2*arr[i]-arr[n-1]);
   }

    return min_arr;
}


int main() {

    int n = 0;
    int m = 0;
    scanf("%d %d", &n, &m);
    int arr[2][22];
    long long ROW[2]; //记录每行的叠加和
    long long COL[22]; //记录每列的叠加和
    int k = 0;
    for (k = 0; k < m; k++)
    {
        COL[k] = 0;
    }
    for (k = 0; k < n; k++)
    {
        ROW[k] = 0;
    }
    int i = 0;
    long long row = 0;
    for (i = 0; i < n; i++)
    {
        int j = 0;
        for (j = 0; j < m; j++)
        {
            scanf("%d", &arr[i][j]);
            row += arr[i][j];
            COL[j] += arr[i][j];
        }
        ROW[i] += row;
    }
    long long s = 0;
    for (k = 0; k < m; k++)
    {
        COL[k] += s;
        s = COL[k];
    }
    long long  min_ROW = 0;
    long long  min_COL = 0;
    //按行寻找 |s_1-s_2| 的最小值；
    min_ROW = Min_arr(ROW, n);
    //按列寻找 |s_1-s_2| 的最小值；
    min_COL = Min_arr(COL, m);
    printf("%lld", min_ROW < min_COL ? min_ROW : min_COL);
    return 0;
}

二维数组前缀和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int h = scanner.nextInt(), w = scanner.nextInt();
        int[][] cake = new int[h][w];
        long[][] presum = new long[h][w];

        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cake[i][j] = scanner.nextInt();

                if (i == 0 && j == 0) {
                    presum[i][j] = cake[i][j];
                } else if (j == 0) {
                    presum[i][j] = presum[i - 1][0] + cake[i][j];
                } else if (i == 0) {
                    presum[i][j] = presum[i][j - 1] + cake[i][j];
                } else {
                    presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + cake[i][j];
                }
            }
        }

        long res = Integer.MAX_VALUE;

        for (int i = 0; i < h; i++) {
            long top = presum[i][w - 1];
            long bottom = presum[h - 1][w - 1] - top;
            res = Math.min(res, Math.abs(top - bottom));
        }
        for (int j = 0; j < w; j++) {
            long left = presum[h - 1][j];
            long right = presum[h - 1][w - 1] - left;
            res = Math.min(res, Math.abs(left - right));
        }
        System.out.println(res);
    }
}

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

int main() {
    ios::sync_with_stdio(false);
    int n, m,tmp;
    long res = INT_MAX;
    cin>>n>>m;

    vector<vector<long>> sum(n+1,vector<long>(m+1,0));
    
    for(int i=1;i<=n;++i){   
       for(int j=1;j<=m;++j){
           cin>>tmp;
           sum[i][j] = tmp+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];       
       }
    }
    for(int j=1;j<=m;++j) res = min(res,abs(sum[n][m]-2*sum[n][j]));
    for(int i=1;i<=n;++i) res = min(res,abs(sum[n][m]-2*sum[i][m]));
    cout<<res;
    return 0;
}

可以把每行每列的求和算一遍存下来供后续二分时重复使用，用 O(n) 的空间把总求和时间压到 O(nlogn)（其实是 O(n)，因为是等比数列求和）

进一步还可以考虑维护以行或列为粒度的前缀和数组，把二分的时间压到 O(logn)

n, m = [int(x) for x in input().strip().split()]

a = [[0] * m for i in range(n)]
row_sum = [0] * n
col_sum = [0] * m
total_sum = 0

for i in range(n):
    a[i] = [int(x) for x in input().strip().split()]
    row_sum[i] = sum(a[i])
    total_sum += row_sum[i]

for j in range(m):
    col_sum[j] = sum([a[i][j] for i in range(n)])

half = total_sum >> 1

# row_idx
l = 0; r = n - 1
if l == r:
    min_row = total_sum
else:
    while (l < r):
        mid = l + r + 1 >> 1
        half_sum = sum(row_sum[:mid])
        if half_sum <= half:
            l = mid
        else:
            r = mid - 1
    if half_sum > half:
        half_sum -= row_sum[mid-1]
    min_row = min(total_sum - 2 * half_sum, 2 * (half_sum + row_sum[r]) - total_sum)

# col_idx
l = 0; r = m - 1
if l == r:
    min_col = total_sum
else:
    while (l < r):
        mid = l + r + 1 >> 1
        half_sum = sum(col_sum[:mid])
        if half_sum <= half:
            l = mid
        else:
            r = mid - 1
    if half_sum > half:
        half_sum -= col_sum[mid-1]
    min_col = min(total_sum - 2 * half_sum, 2 * (half_sum + col_sum[r]) - total_sum)

print(min(min_row, min_col))