题解 P2827 【蚯蚓】
aiyougege
2018-05-01 11:06:33
### 蚯蚓
#### ***80分***
首先这道题可以用*合并果子*的思路做, 合并果子是找到两个最小的并合并, 而这道题是找到最大的拆分.实际上是差不多的.
如何处理每次的将每只蚯蚓加一定长度呢?或许可以转变思路, 每次只有两只蚯蚓没被加其他的全部被加了, 根据**运动是相互**的, **除了那被切成的两只蚯蚓**其他的都往**正方向**移动了一些, 等价于那两只往**负方向**移动了一些. 所以可以记录**累计加**的长度, 有几只没被加的就减去就好了.
利用*堆*或者是**优先队列**, 保存每只蚯蚓, 然后每次切断就弹出堆顶元素(*蚯蚓*)拆成两只后放入堆.这样做的时间复杂度大概是$O(m\log_2 n)$.根据一些**小细节的处理**当然有快有慢.我前前后后改了不少小细节大概是交了七次.这么做大概就是得到**80-85**分了.
|次数|得分|原因|
|:--:|:--:|:--:|
|4|80|用队列记录每次切的蚯蚓;用数组记录|
|2|85|直接输出被切的蚯蚓|
|1|75|O2|
#### ***100分***
关键点: 发现此题中隐含的**单调性**.
发现**先被切掉**的蚯蚓分成的蚯蚓一定比**后切掉**的蚯蚓分成的蚯蚓大.
假设这两只蚯蚓分别为$a,b$,其中$a>b$.那么它被切成$a_1,a_2$. t秒后, $b$被切成了$b_1,b_2$.此时$a_1,a_2$的长度为$l_{a_1}+t=pl_{a}+t,l_{a_2}+t=(1-p)l_a+t$.而$b_1,b_2$的长度却为$p(l_b+t),(1-p)(1_b+t)$, 容易看出$l_{a_1}>l_{b_1},l_{a_2}>l_{b_2}$.也就是说**根本不需要用一个堆来维护, 它本来就具有一定单调性**.
那么就是说如果蚯蚓$a_1,a_2,\cdots,$满足$a_1>a_2>\cdots$,那么以此分成两只$a_{11},a_{12},a_{21},a_{22},\cdots $.那么$a_{12}>a_{22}>\cdots,a_{11}>a_{21}>\cdots$
那么就可以将这两堆**依次存储**, 加上还没被切过的蚯蚓.每次要切时在这三堆里面选择最大的, 切完再依次放回去.
所以这么做时间复杂度为$O(m)$.再优化一下细节基本上就没问题了.
***结论***: 善于发现题目中隐含的单调性.
Tip:**有些细节需要仔细考虑不然会很惨**
#### Code
##### 80分
```c++
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
priority_queue<int>ans;//优先队列
int n,m,q,u,v,t;
int sigma;//累计加的
double p;
int tot;
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
p=(double)u/v;int tmp;
for(int i=1;i<=n;++i){
scanf("%d",&tmp);
ans.push(tmp);
}
for(int i=1;i<=m;++i){
int top=ans.top()+sigma;//被切的蚯蚓的长度
ans.pop();
int a1=floor(p*(double)top),a2=top-a1;//被切成的两只的长度
a1-=sigma,a2-=sigma;
a1-=q,a2-=q;//需要减去它们俩没加的
ans.push(a1),ans.push(a2);//放回队列
if(i%t==0)printf("%d ",top);//要求输出的第一行
sigma+=q;//累加
}
putchar('\n');//换行
for(int i=1;ans.size();++i){
if(i%t==0)printf("%d ",ans.top()+sigma);//要求输出的第二行
ans.pop();
}
return 0;
}
```
##### 100分
```c++
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#define N 7000005
using namespace std;
bool cmp(const int &a,const int &b){
return a>b;
}
priority_queue<int>ans;
int cut1[N],now[N],cut2[N];
int n,m,q,u,v,t;
int sigma;
double p;
int h,h1,h2;
int t0,t1,t2;
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
p=(double)u/v;int tmp;
for(t0=1;t0<=n;++t0)
scanf("%d",&now[t0]);
--t0;t1=t2=0;h=h1=h2=1;
sort(now+1,now+t0+1,cmp);//对所有蚯蚓从大到小排序
int top;
for(int i=1;i<=m;++i){
if(h>t0){if(cut1[h1]>cut2[h2])top=cut1[h1++];else top=cut2[h2++];}
else if(now[h]>=cut1[h1]&&now[h]>=cut2[h2])top=now[h],++h;
else if(cut1[h1]>=cut2[h2]&&now[h]<=cut1[h1])top=cut1[h1],++h1;
else top=cut2[h2],++h2;
;;;//上述四行都是为了找到应该被切的蚯蚓,写的麻烦细节很多
top+=sigma;
int a1=floor(p*(double)top),a2=top-a1;
sigma+=q;
a1-=sigma,a2-=sigma;
cut1[++t1]=a1,cut2[++t2]=a2;
if(i%t==0)printf("%d ",top);
}
putchar('\n');
for(int i=h;i<=t0;++i)ans.push(now[i]);
for(int i=h1;i<=t1;++i)ans.push(cut1[i]);
for(int i=h2;i<=t2;++i)ans.push(cut2[i]);
for(int i=1;ans.size();++i){
if(i%t==0)printf("%d ",ans.top()+sigma);
ans.pop();
}
return 0;
}
```