--- title: "蚯蚓" created: 2025-11-28 tags: - 算法 --- # 蚯蚓 ## 题目 [蚯蚓](https://www.acwing.com/problem/content/description/135/) ![[image-7118b298.png]] ## 思路分析 拿到题目其实就想到了用优先队列priority\_queue来做（底层是堆） 因为每轮要取一个最大值 把它拆成两部分后又放回去 这用大根堆很容易可以做到 有个巧妙的地方是 除了被切开的蚯蚓外 其他蚯蚓每轮会增长p 那意味着所有的数都得重新变 怎么优化这个步骤呢 让所有数都减去一个p 就变成了 堆里的数据都不变 只要把分成两段的要新增的数据-p即可 到时候取出来最长的那个的时候 把它加上轮数\*p再操作 操作完后再减去p 这样就能用较少操作做相同的事情 但是y总分析 用堆的话 时间复杂度是mlogm m为 $7\*10^6$ 这样一来会到 $10^9$ 以上 会超时 所以得另外想办法 如果先对所有蚯蚓进行排序 第一次切的肯定是最长的那只 那么下一轮呢 显然是从第二长的和刚才切出来的两部分里面选吧 那么不妨用把一个优先队列拆成三个普通队列 原长度a[] 切出来的左部分l[] 切出来的右部分r[] 如果$a1>a2$那么一定有$l1>l2$ $ r1>r2$（原本就更长 切出来的两部分肯定也都更长） 所以只要我有a[]是有序的 l[],r[]其实就是潜在有序的（递减） 那么问题就变成了 每轮把三个队列里的最大值做比较（三个都是递减区间） 然后切出来的分别再插入l[],r[]（一定是l,r里面最小的） 这样时间复杂度就变成了O(1) 同样对于每轮+q的问题能用上面的思路优化 （每一秒钟被切出的新蚯蚓不会变长，给每个新蚯蚓先减q，可以看成所有蚯蚓都加了q） ## 代码实现 ```cpp #include using namespace std; const int N=1e5+10,M=7e6+10; //三个队列 int q1[N],q2[M],q3[M]; int hh1,hh2,hh3,tt1,tt2=-1,tt3=-1; int increase; int n,m,q,u,v,t; bool cmp(int a,int b)//使用sort排序定义从大到小 { return a>b; } int get_max(){ //从三个队列的对头找一个最大的 int x=INT_MIN; if(hh1<=tt1) x=max(x,q1[hh1]); if(hh2<=tt2) x=max(x,q2[hh2]); if(hh3<=tt3) x=max(x,q3[hh3]); //取到了记得把那个出队 if(hh1<=tt1 && x==q1[hh1]) hh1++; else if(hh2<=tt2 && x==q2[hh2]) hh2++; else hh3++; return x; } int main() { cin>>n>>m>>q>>u>>v>>t; for(int i=0;i<=n;i++) cin>>q1[i]; sort(q1,q1+n,cmp); tt1=n-1; for(int i=1;i<=m;i++) { int x=get_max(); //取出来先加上increase x+=increase; int left=x*1ll*u/v; int right=x-left; //把每次切的那条输出（仅输出第n*t秒 而不是每秒） if(i%t==0) cout<