题解 P2827 【蚯蚓】

· · 题解

这题是一个优先队列题目，然而我不会用优先队列，就直接用数组模拟了。（楼下大佬们的题解根本不知啥意思QAQ）

题目分析

一看到这道题，第一个想的是模拟。每次找最大的，然后切一半，其余的都加q。不过由于m会达到7*10^6，n也是10^5，所以一定会超时。

那么我们可以用优先队列，用三个数组A,B,C分别存储xi,⌊pxi⌋和xi−⌊pxi⌋。

让A满足 xi>=xj

那么由于0<p<1，所以B一定满足 ⌊pxi⌋>=⌊pxj⌋

然后可得C满足 xi- ⌊pxi⌋>xj-⌊pxj⌋

但是如果xj后切，那么会加q，但在xj切得那一瞬间，xi又会加q。所以我们要证明 ⌊pxi⌋+q>=⌊p(xj+q)⌋

证：⌊pxi⌋+q>=⌊p(xj+q)⌋

⌊p(xj+q)⌋=⌊pxj+pq⌋

由于0<p<1，所以pq<=q

又由于⌊n⌋<=n，所以⌊pq⌋<=q

所以xj无论何时切，一定不会比xi长，所以xi一定比xj先切。

然后长的长度先不考虑，输出的时候在加上，切掉的就减去加上的q，也就是减q

代码如下：

//--新阶梯工作室防伪水印-- 
//--By新阶梯工作室 闪现--
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>//头文件准备
using namespace std;
const int N=100005,M=8000005;//闪现本人比较懒，定义了一个常量
int n,m,t,q,u,v,del,p[3][M],l[3],r[3],a[N];//然后懒懒的闪现又用了一个二维数组存储，l数组用于存队尾，r数组用于存队首
int main(){
    int now,nowj;
    scanf ("%d %d %d %d %d %d",&n,&m,&q,&u,&v,&t);//这个读入好长啊
    memset(p,128,sizeof(p));//其实我也不知道有什么用
    for (int i=1;i<=n;i++){
        scanf ("%d",&a[i]);
    }
    sort (a+1,a+1+n);//排序
    for (int i=n;i>=1;i--){
        p[0][r[0]++]=a[i];//其实如果按降序排列的话，直接从1模拟到n，不过懒闪现懒得打cmp
    }
    for (int i=1;i<=m;i++){
        now=-1<<30;//好吧，其实只要定义为-1就行了
        for (int j=0;j<3;j++){
            if (l[j]<=r[j]&&p[j][l[j]]>now){//找最大的，找到哪个就切哪个
                now=p[j][l[j]];
                nowj=j;
            }
        }
        l[nowj]++;//然后切的那个队尾就出队
        if (i%t==0)printf ("%d ",del+now);
        p[1][r[1]++]=1ll*(now+del)*u/v-del-q;//关键的一个语句，我一个小时才推导出来
        p[2][r[2]++]=now+del-1ll*(now+del)*u/v-del-q;//同样很关键
        del+=q;//求长了多长
    }
    printf ("\n");
    for (int i=1;i<=n+m;i++){
        now=-1<<30;
        for (int j=0;j<3;j++){
            if (l[j]<=r[j]&&p[j][l[j]]>now){//同上
                now=p[j][l[j]];
                nowj=j;
            }
        }
        if (i%t==0)printf ("%d ",del+now);//输出
        l[nowj]++;//同上，不过队尾是先输出再出队。貌似和这个没有关系
    }
    return 0;
}