首页 > 代码库 > 【uoj264】 NOIP2016—蚯蚓

【uoj264】 NOIP2016—蚯蚓

2024-08-26 13:40:04   222人阅读

http://uoj.ac/problem/264 (题目链接)

题意

　　n条蚯蚓，时间为m。每单位时间要可以将最长的蚯蚓切成len/2和len-len/2两份，长度为0的蚯蚓不会消失，因为每单位时间所有的蚯蚓的长度都会增长L。问当时间T是t的倍数的时候输出当前即将切断的蚯蚓的长度，完成切割后，输出按顺序输出长度排名为t的倍数的蚯蚓的长度。

Solution

　　我们构建3个单调队列，分别记为q[0]，q[1]，q[2]。其中q[0]记录初始时每条蚯蚓的长度，并将其按从大到小的顺序排列。q[1]记录每次切割后长的那一截的长度。q[2]记录每次切割后短的那一截的长度。对于蚯蚓增长的长度，我们可以运用标记的思想，因为每条蚯蚓所增长的长度都是一样的。

　　显然，这样子构出来的3个队列都是单调递减的，于是每次切割，取3个队列队首最大的元素进行切割，假设它的大小为x，当前增长长度为l，每单位时间蚯蚓长度增长L。那么，这条蚯蚓的长度len=x+l，切割后长度记为l1和l2，那么放入队列时将l1和l2都减去L+l，这样它们就可以和整个队列中的元素的标记同步了。

　　需要输出的时候判断一下当前的时间是否是t的倍数即可。

细节

　　切割的时候别用double，精度太萎，UOJ上被hack了。。

代码

// uoj264#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define RG register#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;inline int gi() {	int x=0,f=1;char ch=getchar();	while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1;ch=getchar();}	while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}const int maxn=100010;int n,m,L,u,v,t;int a[maxn];int head[3],q[3][10000010],tail[3];inline bool cmp(int a,int b) {return a>b;}int main() {	n=gi(),m=gi(),L=gi(),u=gi(),v=gi(),t=gi();	memset(q,-0x7f,sizeof(q));	for (int i=1;i<=n;i++) q[0][i]=gi();	sort(q[0]+1,q[0]+1+n,cmp);	int l=0;	head[0]=head[1]=head[2]=1;	tail[0]=tail[1]=tail[2]=0;	tail[0]=n;	for (int x,l1,l2,op,i=1;i<=m;i++) {		op=q[0][head[0]]>q[1][head[1]] ? 0 : 1;		op=q[op][head[op]]>q[2][head[2]] ? op : 2;		x=q[op][head[op]++]+l;		if (i%t==0) printf("%d ",x);		l1=(LL)x*u/v;		l2=x-l1;		q[1][++tail[1]]=max(l1,l2)-l-L;		q[2][++tail[2]]=min(l1,l2)-l-L;		l+=L;	}	puts("");	for (int x,op,i=1;i<=n+m;i++) {		op=q[0][head[0]]>q[1][head[1]] ? 0 : 1;		op=q[op][head[op]]>q[2][head[2]] ? op : 2;		x=q[op][head[op]++]+l;		if (i%t==0) printf("%d ",x);	}	return 0;}

　　

【uoj264】 NOIP2016—蚯蚓


联系
我们