原题
思路概述
题意分析
给定整数 \(n,m,q,u,v,t\) 和一个数列 \(\{a\}\),进行 \(m\) 次操作如下:每次选取其中最大数 \(x\) 切分为 \([px],x-[px](p∈\frac{u}{v})\)。求每 \([\frac{m}{t}]\) 次切分的数大小与完成所有操作后第 \(t,2t,3t\dots\) 大的数字。
思路简述
每次对最大数进行操作,考虑用单调队列,但是在本题的数据规模下可能会超时。
分析题目后可以发现,只需要对初始数列按降序排序后就可以,就可以保证每次切分出的较大或较小段呈递减趋势,因此只需要开三个队列分别存储原始序列、切分后较大数的序列、切分后较小数的序列,然后模拟即可。
算法实现
关于长度计算
由于本题中每一个单位时间除被切分的数之外其他数都会增加 \(p\),因此每个数入队(包括存储原始序列的队列)时需要记录其入队时间以计算其即时长度。公式如下:
\[len_i=val_i+(time_{now}-time_{i})p \]其中 \(len_i\) 为即时长度,\(val_i\) 为入队时的初始长度,\(time_{now},time_i\) 分别为当前时间与该数入队时间。
关于切分数细节问题
由于被切分数在当前时间段内长度不会增长,所以在考虑切分当前数字时对其时间的计算应该引入参数 \(time_{now}-1\) 而非 \(time_{now}\)。
AC code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<ctime>
#define ll long long
#define RL register long long
#define RN register node
using namespace std;
const ll maxn=7e6+10;
ll n,m,q,u,v,t;
ll a[maxn];
typedef struct
{
ll val,tim;
inline ll get_len(ll x){return val+(x-tim)*q;}
}node;
typedef struct
{
ll fst,lst;
node s[maxn];
inline void init(void){fst=lst=0;memset(s,0,sizeof(s));return;}
inline bool empty(void){return fst>=lst;}
inline void push(node x){s[lst]=x;++lst;return;}
inline void pop(void){++fst;return;}
inline node front(void){return s[fst];}
}queue;
queue qr,mx,mn;
inline node max_node(ll ntm);
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> q >> u >> v >> t;
for(RL i=1;i<=n;++i) cin >> a[i];
sort(a+1,a+n+1,greater<ll>());
for(RL i=1;i<=n;++i) qr.push((node){a[i],0});
for(RL i=1,len,res;i<=m;++i)
{
RN temp=max_node(i);
len=temp.get_len(i-1)*u/v;res=temp.get_len(i-1)-len;
mx.push((node){max(len,res),i});
mn.push((node){min(len,res),i});
if(!(i%t)) printf("%lld ",temp.get_len(i-1));
}
putchar('\n');
for(RL lim=n+m,i=1;i<=lim;++i)
{
RN temp=max_node(m);
if(!(i%t)) printf("%lld ",temp.get_len(m));
}
return 0;
}
inline node max_node(ll ntm)
{
RN x=(!qr.empty())?qr.front():(node){0,ntm},y=(!mx.empty())?mx.front():(node){0,ntm},z=(!mn.empty())?mn.front():(node){0,ntm};
RL lx=x.get_len(ntm),ly=y.get_len(ntm),lz=z.get_len(ntm);
if(lx>=ly && lx>=lz)
{
if(!qr.empty()) qr.pop();
return x;
}
else if(ly>=lx && ly>=lz)
{
if(!mx.empty()) mx.pop();
return y;
}
else
{
if(!mn.empty()) mn.pop();
return z;
}
}
标签:node,return,题解,P2827,void,inline,洛谷,include,ll
From: https://www.cnblogs.com/frkblog/p/16817136.html