蚯蚓[NOIP2017-Day2T2](堆优化)

题目

Luogu
$1\le n\le 10^5,1\le m\le 7\times 10^6$
输出的 $t$ 主要是怕你 $T$ 掉

思路

首先暴力模拟加了快读可以得 85 分!
暴力模拟时候注意整体加怎么办
我们可以借鉴相对运动，也就相当于当前蚯蚓分裂的 $a,b$ 减去 $q$ ，基准值加 $q$
然后我们想想，其他蚯蚓的长度是相对静止的，对吧
那假设蚯蚓并不会伸长，我们怎么做
对于一开始的长度递减排序 $S1$
然后砍断的较长的存在 $S2$ 较短的存在 $S3$
发现 $S2$, $S3$ 也是递减的
那如果有伸长呢？
发现是一样的，不过每次进入 $S2,S3$ 需要自身长度-1

代码

暴力

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<ctime>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 7100000
#define INF 0x3f3f3f3f
priority_queue<int> Q;
int Ans[MAXN+5];
int main(){
    int n=read(),m=read(),q=read(),u=read(),v=read(),t=read(),sum=0;double p=1.0*u/v;for(int i=1;i<=n;i++)Q.push(read());int len1=0,len2=(n+m)/t;for(int i=1;i<=m;i++){
    int len=Q.top()+sum;Q.pop();if(i%t==0)Ans[++len1]=len;int a=floor(p*len),b=len-a;sum+=q,a-=sum,b-=sum;Q.push(a),Q.push(b);}for(int i=1;i<=len1;i++){
    printf("%d",Ans[i]);if(i!=len1)putchar(' ');}puts("");int ti=0,cnt=0;while(!Q.empty()){
    int len=Q.top()+sum;Q.pop();ti++;if(ti%t==0){
    printf("%d",len);if(++cnt!=len2)putchar(' ');}}puts("");return 0;
}

100分

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<vector>
#include<ctime>
#include<bitset>
#include<cmath>
#include<cstdio>
#include<climits>
#include<cstdlib>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
#define ULL unsigned long long
int read(){
    bool f=0;int x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return !f?x:-x;
}
#define MAXN 7100000
#define INF 0x3f3f3f3f
int Ans1[MAXN+5],len1;
int S1[MAXN+5],S2[MAXN+5],S3[MAXN+5],tmp[MAXN+5],h1,h2,h3,t1,t2,t3,siz;
bool cmp(int a,int b){
    return a>b;}
int main(){
    int n=read(),m=read(),q=read(),u=read(),v=read(),t=read(),sum=0;double p=1.0*u/v;h1=h2=h3=1,t1=n,t2=t3=0;for(int i=1;i<=n;i++)S1[i]=read();sort(S1+1,S1+t1+1,cmp);for(int i=1;i<=m;i++){
    int len=-INF,cho=-1;if(h1<=t1&&S1[h1]>len) len=S1[h1],cho=1;if(h2<=t2&&S2[h2]>len) len=S2[h2],cho=2;if(h3<=t3&&S3[h3]>len) len=S3[h3],cho=3;len+=sum;if(i%t==0)Ans1[++len1]=len;if(cho==1) h1++;if(cho==2) h2++;if(cho==3) h3++;int a=floor(p*len),b=len-a;sum+=q,a-=sum,b-=sum;S2[++t2]=a,S3[++t3]=b;}for(int i=1;i<=len1;i++){
    printf("%d",Ans1[i]);if(i!=len1)putchar(' ');}puts("");int len2=(n+m)/t,cnt=0;for(int i=1;i<=n+m;i++){
    int len=-INF,cho=-1;if(h1<=t1&&S1[h1]>len) len=S1[h1],cho=1;if(h2<=t2&&S2[h2]>len) len=S2[h2],cho=2;if(h3<=t3&&S3[h3]>len) len=S3[h3],cho=3;len+=sum;if(cho==1) h1++;if(cho==2) h2++;if(cho==3) h3++;if(i%t==0){
    printf("%d",len);if(++cnt!=len2)putchar(' ');}}puts("");return 0;
}