P2827蚯蚓解题报告
无秒
2020-07-01 20:59:10
话说已经有n久都没写博客了，我又变懒了qwq，现在还在写NOIP的题，要么就是改题，模板的话老师说要写，但是不知道写啥（其实自己觉得很多都需要温习巩固一下，但是老师给的那个啥模板没几个会啊，然后在洛谷上搜模板，就把洛谷上我会的都差不多写了，然后一些写过的或者没在洛谷上看到的容易的，都没写，自我批评一下）
好了，进入正题，讲题。写这题主要是有点触动才写。
首先，这一看就是个堆嘛，直接用stl，但是我有点蠢（没吃，我感觉我最近智商下降了很多qwq，但愿我rp++吧），自以为是的想着记录时间，这样子算的更快，但是问题来了，我要开结构体，但是放到队列中又要重载运算符，但是我经过了n多的尝试，不得不放弃（平时写这些重载运算符都是对的啊，为什么会这个丫子，呜呜呜，难道队列要什么特殊的吗），所以我就放弃了记录时间，便直接干脆点，把他们氧化还原一波（变成最开始的情况），就是在算的时候才加上，然后分裂的时候肯定要把q减掉。
代码如下：
```cpp
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstdlib>
#include <functional>
#include <cmath>
using namespace std;
#define isdigit(x) ((x)>='0'&&(x)<='9')
#define ri register int
priority_queue<int,vector<int>,less<int> >qq;
int n,m,q,u,v,t,px,py,sum;
double p;
int a[100010];
inline void read(int &x)
{
x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
inline void write(int x)
{
char s[30];int top(0);
while(x)s[++top]=x%10,x/=10;
if(!top)putchar('0');
else while(top)putchar(s[top--]+'0');
putchar(' ');
}
int main()
{
read(n);read(m);read(q);read(u);read(v);read(t);
p=(double)u/(double)v;
for(ri i=1;i<=n;i++) read(px),qq.push(px);
for(ri i=1;i<=m;i++)
{
py=qq.top()+sum;qq.pop();
if(i%t==0) write(py);
px=floor(p*(double)py);py-=px;
sum+=q;
qq.push(px-sum);qq.push(py-sum);
}
putchar('\n');
for(ri i=1;i<=(n+m)/t*t;i++)
{
if(i%t==0) write(qq.top()+sum);
qq.pop();
}
return 0;
}
```
当然了，要是就这的话，那我也不用讲了，它也不配蓝题。就是其实有小细节，但是我们在考场上会怎么样呢？直接就这么过了。不能拿到满分。
so，我们要在考场上警惕，不能放过一丝一毫。蚯蚓要分成两段，很明显，长的分成的相应的一段必定大点，那么就分成三个数组，不用把它慢慢插入了，虽然只用logn，但在O(1)面前啥都不算qwq。所以呢，看时间复杂度是由提示的。
记起了hsx大佬的第四题，那也是的。本来它就需要你走幻境，你不能直接瞎跑啊，浪费了不少时间。所以正确做法应该是弄到一个点以后，假如它更小，那么就把不在队列，可以到达这个点的点弄进去，也就是把这个点更新了以后更新其他的。这样高效多了是不是？
代码如下：
```cpp
#include <cstdio>
#include <iostream>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
#define isdigit(x) ((x)>='0'&&(x)<='9')
#define ri register int
int cnt1[7000005],cnt2[7000005],now[7000005],qq[7100005];
int n,m,q,u,v,t,px,py,sum;
int h1,h2,h3,r1,r2,r3,tot;
double p;
int a[100010];
inline void read(int &x)
{
x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
}
inline void write(int x)
{
char s[30];int top(0);
while(x)s[++top]=x%10,x/=10;
if(!top)putchar('0');
else while(top)putchar(s[top--]+'0');
putchar(' ');
}
bool cmp(const int a,const int b){return a>b;}
inline int check()
{
if(h3>r3)
{
if(cnt1[h1]>cnt2[h2]) return cnt1[h1++];
else return cnt2[h2++];
}
else if(now[h3]>=cnt1[h1]&&now[h3]>=cnt2[h2]) return now[h3++];
else if(cnt1[h1]>=cnt2[h2]&&cnt1[h1]>=now[h3]) return cnt1[h1++];
else return cnt2[h2++];
}
inline void init()
{
for(int i=h3;i<=r3;i++) qq[++tot]=now[i];
for(int i=h1;i<=r1;i++) qq[++tot]=cnt1[i];
for(int i=h2;i<=r2;i++) qq[++tot]=cnt2[i];
}
int main()
{
read(n);read(m);read(q);read(u);read(v);read(t);
p=(double)u/(double)v;
for(ri i=1;i<=n;i++) read(now[i]);
sort(now+1,now+1+n,cmp);
r3=n;r1=r2=0;h1=h2=h3=1;
for(ri i=1;i<=m;i++)
{
py=check()+sum;
if(i%t==0) write(py);
px=floor(p*(double)py),py-=px;
sum+=q;px-=sum,py-=sum;
cnt1[++r1]=px,cnt2[++r2]=py;
}
putchar('\n');
init();
sort(qq+1,qq+1+tot,cmp);
for(ri i=t;i<=tot;i+=t) if(i%t==0) write(qq[i]+sum);
return 0;
}
```