文章

1

粉丝

186

获赞

4

访问

8.7k

头像
一次刷墙避免超时
P1209
发布于2021年3月24日 14:50
阅读数 8.7k

看了一位同学提交的思路很不错;

开始我是打算对每一次刷墙就使那部分范围的wall的value值+1,最后统计wall值,但显然容易超时。后来发现可以将刷墙过程先不做,每次记录下刷的起点和终点,最后刷一遍就行;

代码如下:

include<bits/stdc++.h>
using namespace std;

int main(){
    int B,E;
    int b,e;
    int wall[200005]={0};
    while(scanf("%d %d",&B,&E)){
        if(B==0&&E==0) break;
        wall[B]++;        //刷墙起点标记
        wall[E+1]--;    //刷墙终点标记
    }
    
    for(int i=1;i<=200005;i++){
        wall[i]+=wall[i-1];    //有标记的可以把后面的赋为相同值,直至遇到下一个标记。由于对刷一次墙来说,起始是正的,终止是负的,刷到终止处后面值为0,表明作用域。
    }
    
    while(scanf("%d %d",&b,&e)){
        if(b==0&&e==0) break;
&...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发