数组等值最小步数求解C程序超时问题优化求助

问题背景 #

给定两个长度为n的数组a和b，每次操作可将a[i]更新为a[i]-b[i]（仅当a[i]≥b[i]时允许执行该操作）。需要计算让数组a所有元素相等的最小操作步数，若无法实现则输出-1。

现有问题 #

本人编写的C语言程序仅通过部分测试用例，在处理含5000个元素的第3个测试用例时出现超时。尝试过通过公式计算步数、修改循环终止条件等优化方法，但效果不理想，寻求有效的性能优化方案。

现有代码 #

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// 检查数组所有元素是否相等
int check_equality(const int *a, const int n);

int main (void) {
    int n = 0;
    int i = 0;
    int min = INT32_MAX;
    int max = 0;
    int steps = 0;

    scanf("%d", &n);

    int *a = calloc(n, sizeof(int));
    if (a == NULL) return 1;

    int *b = calloc(n, sizeof(int));
    if (b == NULL) return 1;
 
    // 读取数组a的数据
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        min = a[i] < min ? a[i] : min; // 获取数组中的最小值
        max = a[i] > a[max] ? i : max; // 获取数组中最大值的索引
    }

    // 读取数组b的数据
    for (i = 0; i < n; i++) {
        scanf("%d", &b[i]);
    }

    // 统计操作步数
    while(check_equality(a, n) != 0) {
        // 若最大值无法再减小且数组元素未全部相等，输出-1
        if (b[max] > a[max]) {
            steps = -1;
            break;
        }
        
        // 统计步数并重新检查最小值和最大值
        for (i = 0; i < n; i++) {
            while(a[i] > min) {
                a[i] -= b[i];
                steps++;
            }
            min = a[i] < min ? a[i] : min;
            max = a[i] > a[max] ? i : max;
        }
    }

    free(a);
    free(b);

    printf("%d\n", steps);

    return 0;
}

int check_equality(const int *a, const int n)
{
    int i = 0;

    for (i = 0; i < n-1; i++) {
        if (a[i] != a[i+1]) {
            return -1;
        }
    }

    return 0;
}

尝试过的优化片段 #

• 公式计算步数，减少循环次数：

  steps += (a[i] - min) / b[i];
  a[i] = min + ((a[i] - min) % b[i]); 
  

• 修改循环终止条件：

  while(min != max && a[max] > b[max])
  

测试用例示例 #

测试用例1 #

输入：
5
5 7 10 5 15
2 2 1 3 5

结果：8

测试用例2 #

输入：
2
5 6
4 3

结果：-1

内容的提问来源于stack exchange，提问作者Juan