[NOIP2016]蚯蚓

思路

对于每条蚯蚓，用一个结构体pair<int,long long>维护它最近一次被切的时间点以及它的长度，同时使用三个队列分别维护原来的蚯蚓、px部分的蚯蚓以及x-px部分的蚯蚓，每次选最长蚯蚓时比较三个队列队头元素即可

Code

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <deque>
#include <tuple>
#include <bitset>
#define ios std::ios::sync_with_stdio(false);std::cin.tie(0)
#define MAXINT 1e9+7
#define ll long long
#define pb push_back
#define mpr make_pair
#define FOR(i,m,n) for(int i = m;i < n;i++)
#define FORR(i,m,n) for(int i = m;i >= n;i--)
#define FOR_epr(i,m,epr) for(int i = m;epr;i++)
#define FORR_epr(i,m,epr) for(int i = m;epr;i--)
using namespace std;

int n,m,q,u,v,t;
double p;
ll a[100010];

void solve(){
    queue<pair<int, ll>> qu[3];    //1->px,2->x-px
    cin>>n>>m>>q>>u>>v>>t;
    p = (u*1.0)/v;
    FOR(i,0,n) cin>>a[i];
    sort(a,a+n,[](ll x,ll y){ return x >= y; });
    //转存至队列first表示切割时间点，second表示长度
    FOR(i,0,n) qu[0].push(mpr(1,a[i]));
    ll tmp = (qu[0].front()).second;
    FOR(i,1,m+1){
        ll mx = -0x3f3f3f3f,flag = -1;
        if(qu[0].size() && ((qu[0].front()).second +
           (i - (qu[0].front()).first)*q > mx)){
            mx = qu[0].front().second + (i - (qu[0].front()).first)*q;
            flag = 0;
        }
        if(qu[1].size() && ((qu[1].front()).second +
           (i - (qu[1].front()).first)*q > mx)){
            mx = qu[1].front().second + (i - (qu[1].front()).first)*q;
            flag = 1;
        }
        if(qu[2].size() && ((qu[2].front()).second +
           (i - (qu[2].front()).first)*q > mx)){
            mx = qu[2].front().second + (i - (qu[2].front()).first)*q;
            flag = 2;
        }
        if(i%t == 0) cout<<mx<<" ";
        qu[1].push(mpr(i+1,floor(mx*p)));
        qu[2].push(mpr(i+1,mx - floor(mx*p)));
        qu[flag].pop();
    }
    cout<<'\n';
    FOR(i,1,n+m+1){
        ll mx = -0x3f3f3f3f,flag = -1;
        if(qu[0].size() && ((qu[0].front()).second +
           (m+1 - (qu[0].front()).first)*q > mx)){
            mx = qu[0].front().second + (m+1 - (qu[0].front()).first)*q;
            flag = 0;
        }
        if(qu[1].size() && ((qu[1].front()).second +
           (m+1 - (qu[1].front()).first)*q > mx)){
            mx = qu[1].front().second + (m+1 - (qu[1].front()).first)*q;
            flag = 1;
        }
        if(qu[2].size() && ((qu[2].front()).second +
           (m+1 - (qu[2].front()).first)*q > mx)){
            mx = qu[2].front().second + (m+1 - (qu[2].front()).first)*q;
            flag = 2;
        }
        if(i%t == 0) cout<<mx<<" ";
        qu[flag].pop();
    }
}

int main(){    
    ios;
    int T = 1;
    //cin>>T;
    while(T--) solve();
    return 0;
}