经典ACM算法合集经典ACM算法合集(9)

3、算法设计：
a. n表示汽车加满油后可行驶n公里，k表示出发地与目的地之间有k个加油站；
b. 定义数组a[k+1]存储加油站之间的距离：用a[i]标记第i个加油站与第i+1个加
油站之间的距离（第0 个加油站为出发地，汽车已加满油；第k+1 个加油站为目的地）；
c. 用m计算加油次数，用t标记在未加油的情况下汽车还能行驶t公里，采用for
循环从出发地开始（即i=0）依次计算加油次数：
① 若a[i]>n，则输出“No Solution”；
② 若t<a[i]，则加油一次：t=n,m++；
③ 行驶a[i]公里后，汽车还能行驶t- a[i]公里；
④ i=k+1时循环结束；
d. m即为所求。

4、源程序：

#include<stdio.h>
main()
{
int i,n,k,t,m,a[10000];
scanf("%d%d",&n,&k);
for(i=0;i<=k;i++)
scanf("%d",&a[i]);
m=0;
t=n;
for(i=0;i<=k;i++)
{
if(a[i]>n)
{
printf("No Solution");
break;
}
else if(t<a[i])
{
t=n; m++;
}
t=t-a[i];
}
if(i==k+1)
printf("%d",m);
return 0;
}


5、算法分析：
主函数内for循环的时间复杂度为O（k），故该算法的时间杂度为O（k）。
实验十一 工作分配问题

1、问题描述：
??设有n件工作分

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(9)全文阅读和word下载服务。