C语言 如何让数组中的所有元素都相等

eh57zj3b  于 9个月前  发布在  其他
关注(0)|答案(1)|浏览(125)

给定两个数组a1,a2,.,an和b1,b2,.,bn。在每一步中,如果ai >= bi,可以设置ai = ai -bi。确定使所有a相等所需的最少步骤数。如果不可能,则打印-1。
代码如下:

#include <stdio.h>

#define YES 1
#define NO 0

int main(){
    int i = 0;
    int a[5] = {5,7,10,5,15};
    int b[5] = {2,2,1,3,5};

    // Counting steps
    int change = YES;
    int steps = 0;

    do {
        change = NO;
        for (i = 0; i < n; i++) {
            if (a[i] >= b[i]) {
                a[i] -= b[i];
                steps++;
                change = YES;
            }
        }

    } while (change);

    // Checking if all a's are equal
    for (i = 0; i < n-1; i++) {
        if (a[i] != a[i+1]) {
            printf("-1\n");
            return 0;
        }
    }

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

    return 0;
}

字符串
问题是,对于样本数据,它的预期结果是8,但我不知道这是怎么可能的。我试着用笔和纸做手工测试,得到这些结果:

// Base data
a = {5, 7, 10, 5, 15};
b = {2, 2, 1, 3, 5};

// After the operations
a = {3, 5, 9, 2, 10}; // First iteration
a = {1, 3, 8, 2, 5}; // Second iteration
a = {1, 1, 7, 2, 0}; // Third iteration
a = {1, 1, 6, 2, 0}; // Fourth iteration


在这一点上,我认为所有的a都不可能变得相等,因为除了一个索引之外,所有的索引都已经达到了最低可能值,但是不相等,所以程序应该返回-1,这实际上是程序打印出来的。
我的方法有什么问题,我怎么能得到预期的结果8?

u0njafvf

u0njafvf1#

将a[1]从7变为5,减去2一次(一步)。将a[2]从10变为5,减去1五次(五步)。将a[4]从15变为5,减去5两次(两步)。即八步,然后每个a[i]都是五。
对于一般的算法,a中最大的元素必须减少到不大于最小的元素。这样做,然后重复,直到所有元素都相同或最大的元素不能减少(因为它小于b中的伙伴)。

相关问题