【NOIP2016】earthwarm

发布于 2016-12-15  485 次阅读


题目大意
每一轮有若干个正整数,每一轮会选出最大的一个(设其为 x)并将 x 用两个数取代之,一个是⌊ × ⌋,一个是x − ⌊ × ⌋,
其中 p 为一个取值范围为(0,1)的实数,而其余的数都会加上一个非负整数 q。一开始有 n 个数,要进行 m 轮操作,问每轮操作删掉的数和最后剩下的数。
f1 ≤ n ≤ 10^5
, 1 ≤ ≤ 7 × 10^6

题目分析:作为一名退役选手沉迷co题解无法自拔。

维护三个单调队列a,b,c表示

1、最开始的数
2、是由某一轮的最大值 x 得到的⌊ × ⌋
3、是由某一轮的最大值 x 得到的x − ⌊ × ⌋

关于证明就不贴了.

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<cassert>
#include<climits>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define INF (2139062143)
typedef long long LL;

int n,m,Q,u,v,t,ha,hb,hc,ta,tb,tc,f,tmp;
LL a[100005],b[7000005],c[7000005],s1,s2;
int main(){
	scanf("%d%d%d%d%d%d",&n,&m,&Q,&u,&v,&t);
	double p=1.0*u/v;
	For (i,n){
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+1+n,greater<LL>());
	ha=0,ta=n;
	For (i,m){
		LL x=-INF;f=0;
		if (ha<ta&&x<a[ha+1]) x=a[ha+1],f=1; 
		if (hb<tb&&x<b[hb+1]) x=b[hb+1],f=2;
		if (hc<tc&&x<c[hc+1]) x=c[hc+1],f=3;
		if (f==1) ha++;else if (f==2) hb++;else hc++;
		x+=1LL*Q*(i-1);
		if (i%t==0)	printf("%lld ",x); 
		s1=x*p; s2=x-s1;
		s1-=1LL*i*Q;s2-=1LL*i*Q;
		b[++tb]=s1;
		c[++tc]=s2;
	}
	printf("\n");
	while (ha<ta||hb<tb||hc<tc){
		tmp++;
		LL x=-INF;f=0;
		if (ha<ta&&x<a[ha+1]) x=a[ha+1],f=1; 
		if (hb<tb&&x<b[hb+1]) x=b[hb+1],f=2;
		if (hc<tc&&x<c[hc+1]) x=c[hc+1],f=3;
		if (f==1) ha++;else if (f==2) hb++;else hc++;
		x+=1LL*Q*m;
		if (tmp%t==0) printf("%lld ",x); 
	}
}

「知我罪我,其惟春秋」