题意:
有n条蚯蚓,在m秒内每一秒选择最长的一条蚯蚓分成二份,其余蚯蚓增长q长度,然后按要求输出。
思路:
用二个队列进行模拟,维护二个队列的单调性,一个队列加入长的,另一个队列加入短的,这样二个队列就是单调的,队列中保持0时刻的长度。
代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=1e12; ll a[100005]; bool cmp(ll a,ll b) { return a>b; } int main() { int n, m, q, u, v, t; scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t); double p=u*1.0/v; queue <ll>q1, q2; for(int i=0;i<n;i++) { scanf("%lld",&a[i]); } sort(a,a+n,cmp); int ji=0; for(int i=1;i<=m;i++) { ll ma=-inf; if(ji<n) { ma=max(a[ji],ma); } if(!q1.empty()) { ma=max(q1.front(),ma); } if(!q2.empty()) { ma=max(q2.front(),ma); } if(ji<n&&ma==a[ji]) { ji++; } else if(!q1.empty()&&q1.front()==ma) { q1.pop(); } else { q2.pop(); } ma=ma+(i-1)*q; if(i%t==0) { //printf("i=%lld t=%d\n",i,t); printf("%lld%c",ma,m/t==i/t?'\n':' '); } ll l=floor(ma*p), r=ma-l; q1.push(l-i*q); q2.push(r-i*q); } if(m<t) { printf("\n"); } for(int i=1;i<=m+n;i++) { ll ma=-inf; if(ji<n) { ma=max(a[ji],ma); } if(!q1.empty()) { ma=max(q1.front(),ma); } if(!q2.empty()) { ma=max(q2.front(),ma); } if(ji<n&&ma==a[ji]) { ji++; } else if(!q1.empty()&&q1.front()==ma) { q1.pop(); } else { q2.pop(); } ma=ma+m*q; if(i%t==0) { printf("%lld%c",ma,(m+n)/t==i/t?'\n':' '); } } if(m+n<t) { printf("\n"); } return 0; }