刷题记录:牛客NC16430[NOIP2016]蚯蚓

传送门:牛客

输入:
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

感觉这道题的思维难度还是有的,洛谷上评级为蓝,牛客三星

首先这道题有一个很显然的暴力做法,就是直接装进一个优先队列里面,再按照题目的意思进行反复更改,但是显然的,毕竟是暴力做法最后被T掉了大概两个点(当然比赛现场已经差不多可以了),但是作为平时的练习,我们肯定是要会正解的

下面就介绍这道题的一种巧妙思路,首先我们会发现假设我们刚开始将我们的蚯蚓按照从大到小排列一遍,我们依次的切断每一条蚯蚓的,假设切断后分别为Ai,Bi',我们会发现Ai,和Bi这两个数列也分别会是单调的,因为我们的比例是一定的,这就有了一个不需要每次都维护单调性,根据这个单调性,我们就不用使用优先队列了,考虑使用普通队列,分别来维护Ai,和Bi,以及刚开始我们的初始队列,然后每次都从三个数列中取出一个最大的即可

解决了储存的问题,接下来的就是如何处理蚯蚓长大的问题了.怎么来维护我们蚯蚓不断的成长呢,我们可以使用类似于线段树的一种懒标记来进行维护,即每次用到我们的这条蚯蚓时,我们再将之前没有加上的成长值给他补上,因为每一次成长值都是一定的,因此此时的维护是十分简单的,并且因为这条蚯蚓被切断之后的这个回合是不会成长的,因此我们此时将这两条蚯蚓减去一回合的成长值即可

到最终我们需要每一条蚯蚓的值之后再采用之前的方式加上一遍懒标记即可

下面是具体代码:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
ll n,m,q,u,v,t;
ll a[maxn];
queue<ll>q1;/*原队列*/queue<ll>q2;/*较大*/queue<ll>q3;/*较小*/
bool cmp(ll a,ll b) {return a>b;}
int main() {
	n=read();m=read();q=read();u=read();v=read();t=read();
	for(int i=1;i<=n;i++) {
		a[i]=read();
	}
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=n;i++) q1.push(a[i]);
	for(int i=1;i<=m;i++) {
		ll maxx=-ll_maxn,pos;
		if(q1.size()) {
			if(q1.front()>maxx) {
				maxx=q1.front();pos=1;
			}
		}
		if(q2.size()) {
			if(q2.front()>maxx) {
				maxx=q2.front();pos=2;
			}
		}
		if(q3.size()) {
			if(q3.front()>maxx) {
				maxx=q3.front();pos=3;
			}
		}
		if(pos==1) q1.pop();
		if(pos==2) q2.pop();
		if(pos==3) q3.pop();
		maxx+=(i-1)*q;
		ll qiuyin1=maxx*u/v;
		ll qiuyin2=maxx-qiuyin1;
		q2.push(qiuyin1-i*q);
		q3.push(qiuyin2-i*q);
		if(i%t==0) {
			printf("%lld ",maxx);
		}
	}
	printf("\n");
	for(int i=1;i<=n+m;i++) {
		ll maxx=-ll_maxn,pos;
		if(q1.size()) {
			if(q1.front()>maxx) {
				maxx=q1.front();pos=1;
			}
		}
		if(q2.size()) {
			if(q2.front()>maxx) {
				maxx=q2.front();pos=2;
			}
		}
		if(q3.size()) {
			if(q3.front()>maxx) {
				maxx=q3.front();pos=3;
			}
		}
		if(pos==1) q1.pop();
		if(pos==2) q2.pop();
		if(pos==3) q3.pop();
		maxx+=m*q;
		if(i%t==0) printf("%lld ",maxx);
	}
	return 0;
}