Luogu P2827 蚯蚓

看到题目就可以想到直接开的堆模拟的过程了吧，这个还是很naive的

注意在用堆做的时候也是要明智一点的，对于蚯蚓长度的相加肯定不能直接遍历并加上，还是可以差分一下的

其实说白了就是把集体加->单体减的一个小技巧，还是挺常用的。

然后看这个数据范围猜想应该是有什么\(O(n)\)的做法的，然后这就要发现题目中隐含的单调性

我们考虑讲所有的蚯蚓分个类，所有初始时没切割过的蚯蚓分为一类，每次切割产生的较长的蚯蚓分为一类，而产生的较短的蚯蚓分为一类

然后我们推到一下就可以发现，对于后面的两类蚯蚓，它们满足单调性

因为我们根据切割的过程可以发现：

先切割的蚯蚓长度一定比后切割的蚯蚓长度长
同一种切法，后切割的一定比先切割的短

所以我们再对初始的蚯蚓长度拍个序，就可以得到三个单调的队列（注意不是单调队列），每一次比较时我们取出队首并切割最长的一只再丢进第二队，第三队即可

差分的思想还是要的，不过这里直接记录了每一只蚯蚓进队的时间，每次注意加上增长的长度

细节比较多，最后对这三队蚯蚓做一次归并即可（因为都是有序的）

因此复杂度为\(O(n\ logn+m)\)

CODE

#include<cstdio>

#include<cctype>

#include<algorithm>

using namespace std;

const int N=100005,M=7000005;

int n,m,q,u,v,t,a[N],que[3][M],num[3][M],H[3],T[3],cut[M],ans[N+M],temp[N+M],cnt,tot;

inline char tc(void)

{

	static char fl[100000],*A=fl,*B=fl;

	return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;

}

inline void read(int &x)

{

	x=0; char ch; while (!isdigit(ch=tc()));

	while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));

}

inline void write(int x)

{

	if (x>9) write(x/10);

	putchar(x%10+'0');

}

inline bool cmp(int x,int y)

{

	return x>y;

}

inline void swap(int &a,int &b)

{

	int t=a; a=b; b=t;

}

inline void merge(void)

{

	register int i=H[0],j=H[1];

	while (i<=T[0]&&j<=T[1])

	if (que[0][i]+(m-num[0][i])*q>que[1][j]+(m-num[1][j])*q) temp[++cnt]=que[0][i]+(m-num[0][i])*q,++i;

	else temp[++cnt]=que[1][j]+(m-num[1][j])*q,++j;

	for (;i<=T[0];++i) temp[++cnt]=que[0][i]+(m-num[0][i])*q;

	for (;j<=T[1];++j) temp[++cnt]=que[1][j]+(m-num[1][j])*q;

	i=1; j=H[2];

	while (i<=cnt&&j<=T[2])

	if (temp[i]>que[2][j]+(m-num[2][j])*q) ans[++tot]=temp[i],++i; else ans[++tot]=que[2][j]+(m-num[2][j])*q,++j;

	for (;i<=cnt;++i) ans[++tot]=temp[i];

	for (;j<=T[2];++j) ans[++tot]=que[2][j]+(m-num[2][j])*q;

}

inline void print(void)

{

	for (register int i=t;i<=m;i+=t)

	write(cut[i]),putchar(' '); putchar('\n');

	for (register int i=t;i<=n+m;i+=t)

	write(ans[i]),putchar(' ');

}

int main()

{

	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);

	register int i,j; read(n); read(m); read(q); read(u); read(v); read(t);

	for (i=1;i<=n;++i) read(a[i]); sort(a+1,a+n+1,cmp);

	for (i=1;i<=n;++i) que[0][++T[0]]=a[i]; H[0]=H[1]=H[2]=1;

	for (i=1;i<=m;++i)

	{

		int len=-1,id;

		for (j=0;j<3;++j)

		if (H[j]<=T[j]) if (que[j][H[j]]+(i-num[j][H[j]]-1)*q>len) len=que[j][H[j]]+(i-num[j][H[j]]-1)*q,id=j;

		cut[i]=len; ++H[id]; int x=1LL*len*u/v,y=len-x; if (x<y) swap(x,y);

		que[1][++T[1]]=x; num[1][T[1]]=i; que[2][++T[2]]=y; num[2][T[2]]=i;

	}

	merge(); print(); return 0;

}

巴特西

Luogu P2827 蚯蚓

最新文章

热门文章