题目描述

blablabla

样例

blablabla

队列维护

这道题目如果说,蚯蚓长度不增长的话,也就是这60分,我们是很容易就拿到的,开一个优先队列,打一个priority_queue即可.但是如果说蚯蚓长度增长的话,那么我们就需要换一种思路了,也就是说我们现在必须找性质来维护这道题目.

我们发现如果蚯蚓i被切断后,然后蚯蚓j也被切断,那么我们发现,i蚯蚓的切后两段的长度,都会大于j蚯蚓的切后的两段的长度,因此这里有单调递减的性质.

找到了性质,那么我们完全可以通过三个队列模拟优先队列,一个队列维护切后的第一段,一个队列维护切后的第二段,另外一个队列,里面存储蚯蚓长度,记住长度是从高到低,排好序的长度,那么每一次将被切断的蚯蚓,肯定是这三个队列的队头,因为我们这道题目具有单调递减的性质,所以其实这道题目三个队列,都隐藏着单调队列的性质.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define p u/v
#define fir(i,a,b) for(ll i=a;i<=b;i++)
const int N=1e7+10;
queue<ll> p1,p2,p3;
ll n,m,q,u,v,t,a[N],data;
int cmp(int a,int b)
{
    return a>b;
}
int calc(ll t)
{
    ll x=-1,a=-1,b=-1,c=-1;
    if (!p1.empty())
        a=p1.front()+t*q;
    if (!p2.empty())
        b=p2.front()+t*q;
    if (!p3.empty())
        c=p3.front()+t*q;
    x=max(a,max(b,c));
    if (x==a)
        p1.pop();
    else
    if (x==b)
        p2.pop();
    else
    if (x==c)
        p3.pop();
    return x;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>q>>u>>v>>t;
    fir(i,1,n)
        cin>>a[i];
    sort(a+1,a+1+n,cmp);
    fir(i,1,n)
        p1.push(a[i]);
    fir(i,1,m)
    {
        ll x=calc(i-1);
        if (!(i%t))
            cout<<x<<" ";
        ll now1=x*p;
        ll now2=x-now1;
        p2.push(now1-i*q);
        p3.push(now2-i*q);
    }
    cout<<endl;
    fir(i,1,(n+m))
    {
        ll x=calc(m);
        if (i%t==0)
            cout<<x<<" ";
    }
    return 0;
}