【问题描述】
由于雨水冲刷,长度为N的路面下陷。勤劳的养路工人使用机器恢复路面,机器每天只能对一段路面[L,R]之间的区域进行1个单位深度的填充修补,道路的
路况用下陷的深度表示。请编程输出修好这条路至少需要的天数。
【输入形式】
第一行一个整数N;
第二行N个空格隔开的整数,表示路面的下陷程度。
【输出形式】
一个整数,表示所用的天数。
【样例输入】
6
1 3 2 4 5 3
【样例输出】
6
【样例说明】
6天修补[1,6], [2,6], [2,2], [4,6], [4,5], [5,5]路段即可。
【评分标准】
0<N<100000;
输出正确的答案。
思路:
1、根据题意每天从区间1~N中,依次深度-1,遇到某个深度0时停止作业,所修改的区间就是当日作业区间。
2、独立函数实现一天作业(workForDay)。参数flag为1显示作业过程,如不需要传0。
3、init函数为输入并返回动态数组。
#include <stdio.h>
#include <malloc.h>
int len=0;//路面长度
int *init();//根据输入初始化深度数组,成功返回地址,失败返回NULL
int workForDay(int *dps,int flag);//执行一天填充作业。成功作业返回1,无需作业返回0, 异常返回-1
//flag=1,打印输出作业过程。flag=0,不打印过程
int main()
{
int day=0,re,*dps=NULL;
dps=init();
if(!dps) return 1;
while((re=workForDay(dps,1))==1)
day++;
if(re==-1) return 1;
printf("共作业%d天\n",day);
free(dps);dps=NULL;//在本程序可不释放,但如果多次调用init函数,每次用完数组,需这样释放内存。
return 0;
}
int *init()
{
int i,*dps=NULL;//dps每单位长度对应深度
len=0;
while(len<=0) scanf("%d",&len);//长度必须大于0整数
dps=(int *)malloc(sizeof(int)*len);
if(!dps) return NULL;
for(i=0;(dps[i]=-1) && i<len;i++)
while(dps[i]<0) scanf("%d",&dps[i]);//每个深度必须大于等于0整数
return dps;
}
int workForDay(int *dps,int flag)
{
int i,bn=-1,an=-1;
if(!dps) return -1;
for(i=0;i<len;i++)
{
if(bn==-1 && dps[i]>0)
bn=i+1,an=bn,dps[i]--;
else if(bn!=-1 && dps[i]>0)
an=i+1,dps[i]--;
else if(bn!=-1 && dps[i]==0)
break;
}
if(bn==-1) return 0;
if(flag) printf("当日作业区间为[%d,%d]\n",bn,an);
return 1;
}