首先,你知道这一题可以使用二分法去优化而不是穷举,已经很好了。但是,你没有把二分法写正确。出现了Runtime Error是因为你的程序出现了除0的错误,比方说测试数据为
3 3
1 1 1
你的程序就会除0,错误,正确答案应该是1。
如果不理解程序为什么是错的,可以把测试数据
3 3
100 100 100
模拟运行以下,看看出现了什么问题。正确答案应该是100,而你的程序输出的是75.
最后,下面是我写的程序:
#include
int
main( void )
{
int i, left, right, mid;
int num;
int n, k;
int len[10000];
scanf( "%d%d", &n, &k );
right = 0;
for( i = 0; i < n; ++i ){
scanf( "%d", &len[i] );
if( right < len[i] )
right = len[i];
}
++right;
left = 0;
while( left + 1 < right ){
mid = (left + right ) / 2;
num = 0;
for( i = 0; i < n; ++i ){
if( num >= k )
break;
num += len[i] / mid;
}
if( num >= k )
left = mid;
else
right = mid;
}
printf( "%d\n", left );
return 0;
}
我写了代码,如下:答案应该是对的,只是运算超时,请高手指点一下,哪里的问题补充:这个问题很有难度的哦! 我只会用C 写。不难。 #include