给定两个数组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?
1条答案
按热度按时间u0njafvf1#
将a[1]从7变为5,减去2一次(一步)。将a[2]从10变为5,减去1五次(五步)。将a[4]从15变为5,减去5两次(两步)。即八步,然后每个a[i]都是五。
对于一般的算法,a中最大的元素必须减少到不大于最小的元素。这样做,然后重复,直到所有元素都相同或最大的元素不能减少(因为它小于b中的伙伴)。