BZOJ4721 [Noip2016]蚯蚓

本文版权归ljh2000和博客园共有,欢迎转载,但须保留此声明,并给出原文链接,谢谢合作。

本文作者:ljh2000
作者博客:http://www.cnblogs.com/ljh2000-jump/
转载请注明出处,侵权必究,保留最终解释权!

 

Description

本题中,我们将用符号[c]表示对c向下取整,例如:[3.0」= [3.1」=[3.9」=3。蛐蛐国最近蚯蚓成灾了!隔壁跳
蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。蛐蛐国里现在共有n只蚯蚓(n为正整
数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为a_i(i=1,2,...,n),并保证所有的长度都是非负整数(即:可
能存在长度为0的蚯蚓)。每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)
将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0<p<1的有理数)决定,设这只蚯蚓长度为x,神刀手会将其
切成两只长度分别为[px]和x-[px]的蚯蚓。特殊地,如果这两个数的其中一个等于0,则这个长度为0的蚯蚓也会被
保留。此外,除了刚刚产生的两只新蚯蚓,其余蚯蚓的长度都会增加q(是一个非负整常数)。蛐蛐国王知道这样不
是长久之计,因为蚯蚓不仅会越来越多,还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物,但是
救兵还需要m秒才能到来......(m为非负整数)蛐蛐国王希望知道这m秒内的战况。具体来说,他希望知道:?m秒内
,每一秒被切断的蚯蚓被切断前的长度(有m个数)?m秒后,所有蚯蚓的长度(有n+m个数)。蛐蛐国王当然知道怎
么做啦!但是他想考考你......
 

Input

第一行包含六个整数n,m,q,u,v,t,其中:n,m,q的意义见问题描述;
u,v,t均为正整数;你需要自己计算p=u/v(保证0<u<v)t是输出参数,其含义将会在输出格式中解释。
第二行包含n个非负整数,为ai,a2,...,an,即初始时n只蚯蚓的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。
保证1<=n<=10^5,0<m<7*10^6,0<u<v<10^9,0<=q<=200,1<t<71,0<ai<10^8。
 

Output

第一行输出[m/t]个整数,按时间顺序,依次输出第t秒,第2t秒,第3t秒……被切断蚯蚓(在被切断前)的长度。
第二行输出[(n+m)/t]个整数,输出m秒后蚯蚓的长度;需要按从大到小的顺序
依次输出排名第t,第2t,第3t……的长度。
同一行中相邻的两个数之间,恰好用一个空格隔开。即使某一行没有任何数需要 输出,你也应输出一个空行。
请阅读样例来更好地理解这个格式。
 

Sample Input

3 7 1 1 3 1
3 3 2

Sample Output

3 4 4 4 5 5 6
6 6 6 5 5 4 4 3 2 2
 
 
 
正解:单调队列
解题报告:
 
60分

      考虑每次取出一个最大值这个操作,堆来维护比较方便,但是每次加上一个q似乎不好处理。我们考虑增加一个全局变量tag,表示每个数都需要加上tag,这样就可以避免对于堆中所有元素增加,而只需把每次新的两个元素减去q,再放入堆中即可。具体做法:系统堆维护,每次取出最大元素,然后加上tag,得到真实值,算出两个新元素值,tag加上q,两个新元素值减去tag,丢入堆中。

 

65分

      系统堆常数太大了,加上CCF的评测机的速度有限,30w的点刚好被卡T。换成手写堆即可通过第18个测试点。

 

90分

      注意到q=0同样有很多的部分分,如果我们能解决掉q=0的情况,再加上上述算法,即可获得90分。

      首先q=0表示每次没有自增操作,很容易发现其实所有的元素都是在单调下降(或者说不增)的,也就是说每次取出来的最大元素肯定是不增的,这就说明切掉之后分成的两个新元素,一定比之前任何一次切掉之后的新元素要小。

     这启示我们,似乎在q=0的时候具有单调性。我们维护三个队列q1、q2、q3。初始时q1是从大到小排列的n个数,q2,q3为空。每次操作,取出三个队列的队首元素中最大的那个,设为x,把px丢到q1中,x-px丢到q2中。根据我们上面所说的,我们可以保证任何时候取出来的都是不增的,所以我们可以保证这三个队列在任何时候都是单调不增的。这样就可以通过90%的测试点了。

 

100分

      通过对于q=0时单调性的研究,我们可以发现其实q≠0的时候同样具备单调性。

      我们对于q≠0的时候,假设不满足单调性,即存在之前的某次分割的为a,中间间隔了N轮之后,这次分割的元素在a分割时它为b,则此时为b+N*q,并且b切出来的部分比之前a切出来的要长。假设上述情况存在,则说明满足:

  $${a*p+N*q<(b+N*q)*p(只考虑乘以p的部分)}$$

  因为a>=b,而右边展开之后就变成了$${b*p+N*q*p}$$因为p<1,而a>=b,显然上式不成立。可以通过反证法说明这一点。

  从单调性的角度也可以证明算法的正确性:因为我们每次取出一个元素x,分成两部分,然后把整体加上q,再把这两个新元素-q。是不是意味着在队列中保存的元素的值仍然是单调递减的(因为没有任何加法操作,只会因为被分成两半而变小)?也就是说,不管怎么变,这个全局的增量tag是不会影响相对大小的,因为tag的针对对象是全体元素,所以如果在减掉tag的情况下满足的大小关系加上tag后显然满足,因为同时加上一个数,相对大小并不会改变。所以我们可以发现,在q≠0的时候,队列中的元素同样满足单调性,套用上述算法即可获得满分。

 

 

注意事项

  由于题目中不是直接给出的p,而是通过给出分子分母要求我们自己计算p,来降低精度误差。在乘的时候需要开一个long long的临时变量,除完之后再转成int就可以了。其余的均可只开int。

 
 
 1 //It is made by ljh2000
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <ctime>
 9 #include <vector>
10 #include <queue>
11 #include <map>
12 #include <set>
13 #include <string>
14 using namespace std;
15 typedef long long LL;
16 const int MAXN = 7000011; 
17 const LL inf = (1LL<<60);
18 int n,m,q,t,tag,Q[3][MAXN],head[3],tail[3];
19 LL u,v;
20 
21 inline int getint(){
22     int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
23     if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
24 }
25 inline bool cmp(int q,int qq){return q>qq;}
26 inline void work(){
27     n=getint(); m=getint(); q=getint(); u=getint(); v=getint(); t=getint(); int ljh1,ljh2,from; LL now; int out=0; bool FF=true;
28     for(int i=1;i<=n;i++) Q[0][i]=getint(); sort(Q[0]+1,Q[0]+n+1,cmp); tag=0; head[0]=head[1]=head[2]=1; tail[0]=n; tail[1]=tail[2]=0;
29     for(int i=1;i<=m;i++) {
30         now=-inf; from=-1; for(int j=0;j<3;j++) if(head[j]<=tail[j]) { if(Q[j][head[j]]>now) { now=Q[j][head[j]]; from=j; } }
31         now+=tag; out++; if(out==t) { if(!FF) printf(" "); FF=false; printf("%lld",now); out=0; }
32         ljh1=now*u/v; ljh2=now-ljh1; head[from]++;  tag+=q;
33         ljh1-=tag; ljh2-=tag;
34         Q[1][++tail[1]]=ljh1; Q[2][++tail[2]]=ljh2;    
35     }
36     printf("
"); m+=n; out=0; FF=true;
37     for(int i=1;i<=m;i++) {
38         now=-inf; from=-1; for(int j=0;j<3;j++) if(head[j]<=tail[j]) { if(Q[j][head[j]]>now) { now=Q[j][head[j]]; from=j; } }
39         now+=tag; out++; if(out==t) { if(!FF) printf(" "); FF=false; printf("%lld",now); out=0; }
40         head[from]++;
41     }
42 }
43 
44 int main()
45 {
46     work();
47     return 0;
48 }
原文地址:https://www.cnblogs.com/ljh2000-jump/p/6184271.html