NOIP2016蚯蚓

本文主要是介绍NOIP2016蚯蚓，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

蚯蚓

NOIP2016提高组Day2 T2

绪言

这个题可以用模拟，可以拿到不少的分数（35分），然后现在我能拿到65分，所以先把65分解法拿出来讲讲方法。

结果

先上一下自己代码的结果

把时间限制改大些：

大概就是这样。。。

思路

首先需要知道一件事情。
先切割的长度一定比后切割的长度长。
后切割的一定比先切割的短。
然后就可以把这些数据分为三个部分，这里我（蒟蒻的）用了队列：
a原蚯蚓
b切后的蚯蚓1
c切后的蚯蚓2
原蚯蚓先排序（由大到小），这样每次取队首元素就可以保证其可能为最大长度，切后就可以将切后的两只蚯蚓分类（分为p和1-p两种）放入b，c中。
它的特点就是FIFO（first in first out），借助其特点可以如下进行：
选择要切的蚯蚓时，只需要比较a，b，c三个队列的队首元素，找出最大的数max，切掉后把切后的两个部分分别push到b，c队列末端，最后pop掉这个max所在队列的队首元素（即删除max）。
还要注意，当我们使用p这个变量时，尽量不要提前算出来，要用u/v，这样算出来更准确。
这里还需要有一个每个单位时间加长度的部分，我们如果每次都用O（N）去加长度，那会用掉时间：

这样时间太长了，显然不行。
提出这样一个方法：
设置一个变量len，len表示已经积累的长度。初始化len=0，每回合结束时len+=q，当然在结束前，我们还要考虑这一时刻被切掉的蚯蚓，首先要将最长的蚯蚓标示长度max加上len，也就是说（len+max）是要被切的蚯蚓的长度，这时候如果ti≡0(mod t)【Postscript：就是ti是t的正倍数】就可以输出，然后按照上文所讲的方法push，pop，这里注意push时把被切蚯蚓长度（len+max）*u/v之后还要把它还原回下一局没加过len的情况，即
push(floor((maxx+len)*u/v)-len-q)
与另外一个，不难写出，请读者自己解决（或看下述代码）。
然后输出一个空行。
最后m个回合结束后，要把三个集合都pop出来，存到一个qy[]数组，这样就可以sort排序从大到小排出来，按题意输出即可。

代码

（C++）

#include<iostream>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
int i,j,m,n,q,u,v,t;
long long maxx,ma;
long long len;
int qy[71000001];
int r()
{int ans=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();while(ch>='0'&&ch<='9'){ans*=10;ans+=ch-'0';ch=getchar();}return ans;
}bool cmp(int x,int y)
{return (x>y);
}int main()
{freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);queue<int> a,b,c;n=r();m=r();q=r();u=r();v=r();t=r();for(i=1;i<=n;i++)qy[i]=r();sort(qy+1,qy+n+1,cmp);for(i=1;i<=n;i++)a.push(qy[i]);int ti=0;while(ti<m){maxx=-1000000000;ti++;if(maxx<a.front()) maxx=a.front(),ma=1;if(maxx<b.front()) maxx=b.front(),ma=2;if(maxx<c.front()) maxx=c.front(),ma=3;if(ma==1){b.push(floor((maxx+len)*u/v)-len-q);c.push((maxx+len)-floor((maxx+len)*u/v)-len-q);a.pop();}if(ma==2){b.push(floor((maxx+len)*u/v)-len-q);c.push((maxx+len)-floor((maxx+len)*u/v)-len-q);b.pop();}if(ma==3){b.push(floor((maxx+len)*u/v)-len-q);c.push((maxx+len)-floor((maxx+len)*u/v)-len-q);c.pop();}if(ti%t==0)cout<<maxx+len<<" ";len+=q;n++;}cout<<endl;i=1;while(!a.empty()){qy[i]=a.front()+len;i++;a.pop();}while(!b.empty()){qy[i]=b.front()+len;i++;b.pop();}while(!c.empty()){qy[i]=c.front()+len;i++;c.pop();}sort(qy+1,qy+n+m+1,cmp);for(i=1;i<=n;i++)if(i%t==0)cout<<qy[i]<<" ";cout<<endl;}

结束语

这个题用到了queue，当然还有dalao用了堆（效果更好）。对此表示我对堆这个东西还不大熟悉，革命尚未成功，同志仍需努力。

这篇关于NOIP2016蚯蚓的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---