样例输出的3,改过但不知道哪里有问题。

P1047 [NOIP2005 普及组] 校门外的树

Joseph_J @ 2023-09-06 20:54:32

rt,我将树的状态(已经被砍或未被砍)设为bool,个人认为能避免重叠的情况,请dalao们看看有没有问题

#include<bits/stdc++.h>

using namespace std;
int l,m,num=0;//num为计数器 
int u[10010],v[10086];
bool tree[10010];//判断该位置树是否被砍 
int main(){

    cin>>l>>m;
    memset(tree,1,sizeof(0));//全部的树最开始都没被砍 
    for(int i=1;i<=m;i++) cin>>u[i]>>v[i];

    //坐标内的树被砍,被砍的树==(差+1) 
    for(int i=1;i<=m;i++){
        for(int q=u[i]-1;q<=v[i];q++){

            tree[q]=0;//被砍 
        }
    }

    for(int i=1;i<=l;i++){

        if(tree[i]==1) num++;//还健在就计数 
    }
    cout<<num;

    return 0; 
}

by Soojin2012 @ 2023-09-06 21:03:28

for(int q=u[i]-1;q<=v[i];q++)的q=u[i]-1改成q=u[i]应该就好了(我也是第一次帮人改代码)


by Joseph_J @ 2023-09-06 21:06:57

@zhengshuyue52 OK我试试


by Soojin2012 @ 2023-09-06 21:09:39

不好意思,可能改错了,但可以参考一下我的代码(思路差不多)


by xkseed @ 2023-09-22 14:40:24

memset(tree,1,sizeof(0tree)); // 全部的树最开始都没被砍

存放树的数组初始化有问题


by Joseph_J @ 2023-10-27 16:52:43

@xkseed 也不太对啊全WA了现在


by xkseed @ 2023-11-30 11:19:51

@s1mple__navi

首先,数组只初始化了一部分,完整初始化如下:

memset(tree,1, 10010 * sizeof(0) );

第二,被砍的树 = 右 - 左 + 1,这条逻辑用错了;程序里实现方法是标记被砍的数,只需要标记范围内的树,不需要左界 - 1

for(int q=u[i];q<=v[i];q++){

第三,树的序号是从零开始的(大部分数组都是),需要更改:

for(int i=0;i<=l;i++){
        if(tree[i]==1) num++;//还健在就计数 
    }

by Joseph_J @ 2023-12-01 15:21:49

@xkseed 谢谢,已AC,此帖结


|