Question

杭电acm http://acm.hdu.edu.cn/showproblem.php?pid=2015

这道题为什么当后面的数能被整除时，时间就会变为无限？

#include<stdio.h>
int main()
{
int n,m,i,c,flag;
int sum;
while(scanf("%d %d",&n,&m)!=EOF)
{
flag=0;
sum=0;
c=0;
for(i=1;i<=n;i++)
{
sum+=2*i;
c++;
if(c==m)
{
sum/=m;
if(flag)
printf(" ");
printf("%d",sum);
flag++;
c=0;
sum=0;
}
}
if(c!=m)
{
sum/=c;
printf(" %d",sum);
}
printf("\n");
}
return 0;
}

Answer 1

你好，我是天津大学ACM-ICPC参赛队tri_together队伍的SuperHacker,这里是一份复杂度更低的AC代码，后面有数理解释。
#include <stdio.h>

int main()
{
int m, n, count, last;
int first, delta;
while (scanf("%d%d", &n, &m) != EOF)
{
delta = 2 * m;
first = (2 + delta) / 2;
if (n <= m)
{
printf("%d\n", (2 + 2 * n) / 2);
continue;
}
printf("%d", first);
count = 1;
while ((n -= m) > m)
printf(" %d", first + count++ * delta);
last = 2 + count * delta;
printf(" %d\n", last + (n - 1));
}
return 0;
}

首先要意识到，这个题数据很水，故可以用O(n)的方法水过，但是，当n和m都变得很大时，此方法便不再适用。
从降低时间复杂度的角度考虑，应当设计O(n/m)的方法。
通过分析，可以看出，对于前面由m个数取平均得到的数列，本质上是一个以(a_1 + a_m) / 2为首项2*m为公差的等差数列。而最后一个数需要另外计算。
另外，如果n<=m，需要特别考虑，实际只有一个数为(2+2*n) / 2。
代码中first为首项，delta为公差
每当n = n-m > m时，就继续输出一个数项，首项+count*公差。
但输出最后一个数时，实际数列中假设只余n<m项，此时，最后一个平均值的计算首项为last = 2 + count * delta, 尾项为last + (n - 1) * 2, 根据平均值的计算公式，的一得出，最后的平均值为(last + last + (n - 1) * 2) * n / 2 / n = last + n - 1;

Answer 2

假如最后一组c==m怎么办？c会被你置成0，必然的c！=m ，最后一个判断会继续啊，而且除数为c（且为零）。所以就会出错啊。
另外。空格和回车的处理可以放在一起（不是最后一个就空格，是最后一个就回车）。