二分

二分

https://ac.nowcoder.com/acm/problem/207053

思路:差分
数据范围比较大,所以考虑把数据离散化掉,因为我们只在意相对大小,不在意具体数值。
对于符号是 . 则cnt[pos]++,cnt[pos+1]--
对于符号是 + 则cnt[0]++,cnt[pos]--
对于符号是 - 则cnt[pos+1]++

然后前缀和一下,更新最值即可。
这样子你会发现过了80%的数据,还有20%的数据过不了(你猜我怎么知道的)

考虑一下这样的情况
5-
8+
显然答案取6或者7,结果是2最大。
如果按照上述方式,因为离散化后,5是1,8是2,其实答案可以是5到8之间的数字,但离散化后,我们就把这一段区间的数字都忽略掉了。

所以离散化出来的pos,只需要pos*=2即可,这样扩大了相邻两个数之间的间隔(保证两个数离散化后的之间起码有一个空)
然后就可以ac了

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define x first
#define y second
pair<int,char> a[1000005];
int b[1000005];
int cnt[1000105];
signed main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
        b[i]=a[i].x;
    }
    sort(b+1,b+1+n);
    int m=unique(b+1,b+1+n)-b-1;
    for(int i=1;i<=n;i++){
        int pos=lower_bound(b+1,b+m+1,a[i].x)-b;
        pos*=2;
        if(a[i].y=='.'){
            cnt[pos]++;
            cnt[pos+1]--;
        }
        else if(a[i].y=='+'){
            cnt[0]++,cnt[pos]--;
        }
        else{
            cnt[pos+1]++;
        }
    }
    int ans=cnt[0];
    for(int i=1;i<=200005;i++){
        cnt[i]+=cnt[i-1];
        ans=max(ans,cnt[i]);
    }
    cout<<ans<<endl;
    return 0;
}
全部评论
2 7 - 8 + 这个数据的输出应当是1,这个程序会输出2( 是不是应该在“被离散的两个数之间确实有间隔”的时候才人为添加一个间隙(
点赞 回复 分享
发布于 2023-12-27 21:50 湖北
%%%%%%%%%%%
点赞 回复 分享
发布于 2022-08-29 10:20 安徽
dalao🐮🍺,这20%数据卡了我好久。
点赞 回复 分享
发布于 2022-07-07 19:59

相关推荐

不愿透露姓名的神秘牛友
07-01 11:27
点赞 评论 收藏
分享
点赞 评论 收藏
分享
半解316:内容充实,细节需要修改一下。 1,整体压缩为一页。所有内容顶格。 2,项目描述删除,直接写个人工作量 修改完之后还需要建议,可以私聊
点赞 评论 收藏
分享
重生我想学测开:嵌入式的问题,我准备入行京东外卖了
点赞 评论 收藏
分享
评论
8
2
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务