主页
搜索
最近更新
数据统计
申请密钥
系统公告
1
/
1
请查看完所有公告
P2827 [NOIP2016 提高组] 蚯蚓--注释
最后更新于 2025-07-31 08:04:46
作者
BigSmall_En
分类
个人记录
复制 Markdown
查看原文
删除文章
更新内容
# P2827 [NOIP2016 提高组] 蚯蚓 [https://www.luogu.com.cn/problem/P2827](题目链接) ## 前言 太有意思的一道题目了! 虽然看上去十分简单,只需要模拟+单调队列维护,但这样效率太低,时间复杂度$O(mlog_2n)$,明显会爆炸(也不至于是一道蓝题) ## 基本思路 其实这题的还有隐藏的单调性,那就是对于一条蚯蚓来说: **在前面先分割的蚯蚓的两端一定是比后面分割的蚯蚓的两端分别要长的**。 基于这一特点可以定义三个队列来维护现在的最大值。 $q1$就是等待分割的蚯蚓,$q2$就是分割的蚯蚓中长的那一段,$q3$就是分割的蚯蚓中短的那一段。 这样子的话$q1,q2,q3$的单调性都是能保证的。 而$getfront()$就是找到三个队列开头最大的那个,这就是该分割的蚯蚓。 $inqueue$就是将分割的两端蚯蚓按情况进入队列$q2,q3$。 而这题蚯蚓的长度每一时刻还要增加,如果暴力算的话时间复杂度会上一个维度。 可以考虑用$derta$记录,同时注意找最大值时候把$derta$算上来分割,这样得到的两端是全新且正确的,故进队时候要减去$derta$ 这样时间复杂度就可以到$O(n)$了~~(就是常数有点大)~~ ## 注意点 1.这题的数据范围很坑,$m<=10^6,n<=10^5$,因为分割后蚯蚓的数量会变化,所以$kMAXN=m+n=1.1*10^6$ 2.在查找队首最大元素的时候一定要赋初值为-INF。因为进队的蚯蚓长度是一个相对的基准长度,基准长度+derta才是这一时刻该蚯蚓的真实长度,而该基准长度可能为一个负数。 ## 代码 ```cpp #include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const ll N=7100006;//数组开小了,是7e6//前面说错了,因为还有可能分割后数量变多,还要加一个原来条数1e5 ll n,m,q,u,v,t,a[N],ans[N],derta,top; queue<ll> q1,q2,q3; ll read(){ ll sum=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='1')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-48;ch=getchar();} return sum*f; } ll getfront(){//找三个队列队首最大值 ll x1,x2,x3;x1=x2=x3=-(1<<30);//搞了半天终于这里错了而且为啥要这么写,因为你是用derta计算的,这样入队可能是负数 if(!q1.empty())x1=q1.front(); if(!q2.empty())x2=q2.front(); if(!q3.empty())x3=q3.front(); //cout<<"getfront()"<<x1<<' '<<x2<<' '<<x3<<endl; if(x1>=x2&&x1>=x3){q1.pop();return x1;} if(x2>=x1&&x2>=x3){q2.pop();return x2;} q3.pop();return x3; } void inqueue(ll x1,ll x2){//将新增的两条蚯蚓分长度压入q2,q3中 if(x1<x2){swap(x1,x2);} q2.push(x1),q3.push(x2); return; } bool cmp(ll x,ll y){return x>y;} int main(){ n=read(),m=read(),q=read(),u=read(),v=read(),t=read(); for(ll i=1;i<=n;++i)a[i]=read(); sort(a+1,a+1+n,cmp); for(ll i=1;i<=n;++i)q1.push(a[i]); for(ll i=1;i<=m;++i){//枚举m秒内的操作 ans[i]=getfront()+derta; ll x1=ans[i]*u/v,x2=ans[i]-x1;//反正要下取整,还不如直接算 derta+=q;//根据题意,要在这里计算 //cout<<"inque"<<x1-derta<<' '<<x2-derta<<endl; inqueue(x1-derta,x2-derta);//因为是新的蚯蚓,他的长度是享受不到之前的derta的 } while(!q1.empty()||!q2.empty()||!q3.empty()){a[++top]=getfront()+derta;}//剩下的降序存储,a数字也算废物利用 for(ll i=t;i<=m;i+=t)printf("%lld ",ans[i]);printf("\n"); for(ll i=t;i<=top;i+=t)printf("%lld ",a[i]);printf("\n"); return 0; } // 1.31s / 166.08MB / 1.57KB C++ ```
正在渲染内容...
点赞
0
收藏
0