[NOIP 2016] 蚯蚓

[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=4721

[算法]

首先，我们可以维护一个堆，堆中存放蚯蚓的长度，由于除当前蚯蚓其他的蚯蚓长度都要增加q，我们不妨将当前蚯蚓长度减去q，期望得分85pts

进一步观察，我们发现，同一种切法，早切的蚯蚓一定比晚切的长，根据这个性质，维护三个单调队列，分别维护未被切割的蚯蚓长度，被切割过的蚯蚓长度中较长的那些的长度，被切割的蚯蚓长度中较短的那些的长度，时间复杂度O(M),可以通过所有数据

[代码]

注意为了避免精度误差，需使用long double类型，否则可能无法通过UOJ Extra Test

#include<bits/stdc++.h>

using namespace std;

const long long INF = 1e18;

const long long MAXN = 1e7;

long long i,n,m,u,value,t,x,y,mx,pos,v;

long long head[],tail[],ans1[MAXN],ans2[MAXN];

long long q[][MAXN];

template <typename T> inline void read(T &x)

{

        long long f = ; x = ;

        char c = getchar();

        for (; !isdigit(c); c = getchar())

        {

                if (c == '-') f = -f;

        }

        for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';

        x *= f;

}

int main()

{

        read(n); read(m); read(value); read(u); read(v); read(t);

        for (i = ; i <= n; i++)

        {

                read(x);

                q[][++tail[]] = x;

        }

        head[] = head[] = head[] = ;

        sort(q[] + ,q[] + tail[] + ,greater<long long>());

        for (i = ; i <= m; i++)

        {

                mx = -INF;

                if (head[] <= tail[] && q[][head[]] > mx)

                {

                        mx = q[][head[]];

                        pos = ;

                }

                if (head[] <= tail[] && q[][head[]] > mx)

                {

                        mx = q[][head[]];

                        pos = ;

                }

                if (head[] <= tail[] && q[][head[]] > mx)

                {

                        mx = q[][head[]];

                        pos = ;

                }

                ans1[i] = mx + (i - ) * value;

                head[pos]++;

                x = (long long)((mx + (i - ) * value) * (long double)1.0 * u / v) - i * value;

                y = mx + (i - ) * value - (long long)((mx + (i - ) * value) * (long double)1.0 * u / v) - i * value;

                q[][++tail[]] = max(x,y);

                q[][++tail[]] = min(x,y);

        }

        for (i = ; i * t <= m; i++) printf("%lld ",ans1[i * t]);

        printf("\n");

        for (i = ; i <= n + m; i++)

        {

                mx = -INF;

                if (head[] <= tail[] && q[][head[]] > mx)

                {

                        mx = q[][head[]];

                        pos = ;

                }

                if (head[] <= tail[] && q[][head[]] > mx)

                {

                        mx = q[][head[]];

                        pos = ;

                }

                if (head[] <= tail[] && q[][head[]] > mx)

                {

                        mx = q[][head[]];

                        pos = ;

                }

                ans2[i] = mx + m * value;

                head[pos]++;

        }

        for (i = ; i * t <= n + m; i++) printf("%lld ",ans2[i * t]);

        printf("\n");

        return ;

}