算法竞赛刷题|NOIP2016D2T2-蚯蚓
问题描述 【算法竞赛刷题|NOIP2016D2T2-蚯蚓】本题中，我们将用符号?c? 表示对 c 向下取整，例如：?3.0?=?3.1?=?3.9?=3 。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 n 只蚯蚓（ n 为正整数）。每只蚯蚓拥有长度，我们设第 i 只蚯蚓的长度为 ai (i=1,2,…,n )，并保证所有的长度都是非负整数（即：可能存在长度为 0 的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 p （是满足 0 < p<1 的有理数）决定，设这只蚯蚓长度为 x ，神刀手会将其切成两只长度分别为 floor?px? 和 x??px? 的蚯蚓。特殊地，如果这两个数的其中一个等于 0 ，则这个长度为 0 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 q （是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 m 秒才能到来……（ m 为非负整数）
蛐蛐国王希望知道这 m 秒内的战况。具体来说，他希望知道：
m 秒内，每一秒被切断的蚯蚓被切断前的长度（有 m 个数）；
m 秒后，所有蚯蚓的长度（有 n+m 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你……
输入格式：
输入格式：
第一行包含六个整数n,m,q,u,v,t ，其中：n,m,q 的意义见问题描述； u,v,t 均为正整数；你需要自己计算 p=u/v （保证 0
3 7 1 1 3 1
3 3 2样例输出：
3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2思路分析&代码： 1.先就想到了set，于是就用了set于是就写了一个智障代码，CE，因为set只能用迭代器..
智障代码
#include
#include
#include
using namespace std;
int main(){
set s;
int n,m,q,u,v,t;
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;
i<=n;
i++){
int a;
cin>>a;
s.insert(a);
}
double p=u/v;
for(int i=1;
i<=m;
i++){
int t2=s[n+m-2];
if(i%t==0)cout<2]<<" ";
s.erase(s[m+n-2]);
for(int i=m+n-3;
i>=0;
i--)s[i]+=q;
s.insert(int(p*t2));
s.insert(t2-int(p*t2));
}
cout< set是从小到大排序且set的迭代器不可以执行it+变量，只能用it++运算符，所以我就写了一个结构体，重载<运算符，如下
struct QY{
int l;
bool operator < (const QY& b)const{
if(this->l>b.l)return true;
return false;
}
};
总算是有一个从大到小的序列了，但是set有一个问题就是，集合是不可重复的！所以又写了一个map记录一个长度出现了多少次如果次数为0就在set里删除元素，于是就有了：
void myinsert(QY a){
if(!cnt.count(a.l)){cnt[a.l]=0;
s.insert(a);
}
cnt[a.l]++;
return;
}void myerase(QY a){
cnt[a.l]--;
if(cnt[a.l]==0){cnt.erase(a.l);
s.erase(a);
}
return;
}然后就是一波模拟，但是map慢。。。TLE了13组，所以说这是不可行的
WA+TLE代码（set+map）
#include
#include
#include
#include map慢让我们不得不去找一种其他方法
1.pair<数据，出现次数>
2.结构体里加个出现出现次数
但两个办法有个问题就是set查找会出现查不了，因为查的时候不知道出现次数s.count()括号里数据类型是结构体或pair而参数数不全是不可以的
所以set不行
再想有什么类似于set但数据可重复？
优先队列！
但是有一个问题是优先队列没有指针！不可能用迭代器的方式修改数据（增加蚯蚓长度）当然，可以加一个时间戳（入队时间），就像lazy标记一样在使用时加上（（当前时间-时间戳）*q），但是时间戳怎么存呢？这回连map都不行了，长度一样时间戳可能不同！，所以不可行，还有办法，例如
在时间为i的时候要入队，那么就给这个要入队的数据减去i*q那么在出队的时候我就认为他是在开始时入队的，加上出队时间*q正好抵消掉减的那一部分了，而且后来者数据就是小不需要考虑因为延时带来的出队出错！至于优先队列的常数大，会被卡，最多80分（开了O2优化也是），这是我们可以用下面的三队列的方法
优先队列代码
#include
#include
#include
#include
using namespace std;
priority_queue que;
int m,n,q,u,v,t,add=0;
int main(){
cin>>n>>m>>q>>u>>v>>t;
for(int i=1;
i<=n;
i++){
int tmp;
scanf("%d",&tmp);
que.push(tmp);
}
for(int i=1;
i<=m;
i++){
int tmp=que.top();
que.pop();
tmp+=add;
int a=(long long)tmp*u/v;
int b=tmp-a;
que.push(a-add-q);
que.push(b-add-q);
if(i%t==0)printf("%d ",tmp);
add+=q;
}
printf("\n");
for(int i=1;
i<=n+m;
i++){
if(i%t==0)printf("%d ",que.top()+add);
que.pop();
}
return 0;
} 还有办法：
假设有两只蚯蚓长度分别为x，y，且x>y；那么根据题意x一定被先切，于是我们假设y在x被切后i秒被切。
假设x被切成x1和x2两段，y被切成y1和y2两段；
假设x1>x2 y1>y2随便写的，这个关系怎么写都可以
那么x1>y1,x2>y2
于是我们开3个队列
qs存储未被切的，(已从大到小排序)
q1存储 p*x，
q2存储 x-p*x;
由前面可得每个队列都是单调的（此处即由大到小的)
于是每次取3个堆首的最大元素模拟即可
关于时间戳同上
三队列代码
#include
#include
#include
#include
#include using namespace std;
queueqq,q1,q2;
int n,m,q,u,v,t,tmp[100050],add=0;
int cmp(int a,int b){return a>b;
}int getfront(queue &q){
if(q.empty())return -0x3f3f3f3f;
return q.front()+add;
}int compare_each_front(){
int a=getfront(qq),b=getfront(q1),c=getfront(q2);
int maxn=max(a,max(b,c));
if(maxn==a) qq.pop();
else if(maxn==b) q1.pop();
else if(maxn==c) q2.pop();
return maxn;
}int main(){
cin>>n>>m>>q>>u>>v>>t;
for(int i=0;
i 推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- Guava|Guava RateLimiter与限流算法
- 一个选择排序算法
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- LeetCode算法题-11.|LeetCode算法题-11. 盛最多水的容器（Swift）
- 虚拟DOM-Diff算法详解
- 《数据结构与算法之美》——队列
- 算法回顾（SVD在协同过滤推荐系统中的应用）
- 历史上的今天|【历史上的今天】2 月 16 日（世界上第一个 BBS 诞生；中国计算机教育开端；IBM 机器人赢得智能竞赛）