蚯蚓
题目 蚯蚓
思路分析
拿到题目其实就想到了用优先队列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）
代码实现
#include<bits/stdc++.h>
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<<x<<" ";
increase+=q;
//把除这俩外所有数加increase等于把这俩数减去increase
q2[++tt2]=left - increase;
q3[++tt3]=right - increase;
}
cout<<endl;
//输出最终结果 三路归并（套用归并的思想 每次取出三个里最大的输出）
for(int i=1;i<=n+m;i++)
{
int x=get_max();
if(i%t==0)
cout<<x+increase<<" ";//注意保存的是减去increase的值 要还原一下
}
cout<<endl;
return 0;
}
💬 评论