AcWing 133 蚯蚓 (队列)

标签：wing   des   rip   names   pac   main   +=   ons   long   

https://www.acwing.com/problem/content/description/135/

优先队列，每次将最长的蚯蚓取出来，切开后减去当前的偏移量，再放回队列
但 \(m\) 的范围是 \(7e6\)，显然需要线性做法

线性做法，那就需要考虑一下蚯蚓长度的单调性了，
可以证明，如果 \(x1 > x2\) ,那么新产生的两个蚯蚓长度也是单调递减的
所以就可以维护三个长度递减的队列，每次记得加上偏移量即可

#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;

const int maxn = 100010;

int n, m, Q, v, u, t, delta;
double p;
int a[maxn];

queue q[4];

vector ans1, ans2;

bool cmp(int a, int b){ return a > b; }

ll read(){ ll s=0,f=1; char ch=getchar(); while(ch‘9‘){ if(ch==‘-‘) f=-1; ch=getchar(); } while(ch>=‘0‘ && ch x){
				x = q[1].front();
				num = 1;
			}
			if(q[2].front() > x){
				x = q[2].front();
				num = 2;
			}
		
			q[num].pop();
			if(i % t == 0) ans1.push_back(x + delta);
			part1 = p * (x + delta);
			part2 = (x + delta) - part1;
			delta += Q;
			q[1].push(part1 - delta);
			q[2].push(part2 - delta);
		}
		
		int num, x;
		while(!q[0].empty() || !q[1].empty() || !q[2].empty()){
			if(!q[0].empty()) num = 0, x = q[0].front();
			else if(!q[1].empty()) num = 1, x = q[1].front();
			else num = 2, x = q[2].front();
			
			if(!q[1].empty() && q[1].front() > x){
				x = q[1].front();
				num = 1;
			}
			if(!q[2].empty() && q[2].front() > x){
				x = q[2].front();
				num = 2;
			}
			ans2.push_back(x + delta);
			q[num].pop();
		}
		
		for(int i=0;i

AcWing 133 蚯蚓 (队列)

标签：wing   des   rip   names   pac   main   +=   ons   long   

原文地址：https://www.cnblogs.com/tuchen/p/13938902.html