文章

6

粉丝

0

获赞

9

访问

316

头像
刷出一道墙 C语言题解:差分数组,高效算法
P1209
发布于2026年3月10日 11:58
阅读数 28

#include <stdio.h>
#include <stdlib.h>

int diff[200002];//差分数组、结果数组

int main()
{
    int tb,te,i,up,b,e;
    scanf("%d %d",&tb,&te);
    while(tb!=0||te!=0){
        diff[tb]++;//开始位置值加一
        diff[te+1]--;//末尾下一位值减一
        scanf("%d %d",&tb,&te);
    }
    up=0;//前缀和,可表示前面刷漆的开头部分减前面的结尾部分数量,即当前位置有几层油漆
    for(i=0;i<200002;i++){//将差分数组转化为结果数组
        up+=diff[i];
        diff[i]=up;
    }
    scanf("%d %d",&b,&e);
    while(b!=0||e!=0){
        for(i=b;i<=e;i++){//对每个输入输出结果数组的值
            printf("%d\n",diff[i]);
        }
        scanf("%d %d",&b,&e);
    }
   ...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发