如果x1>x2,那么floor(px1)>floor(px2),且x1-floor(px1)>x2-floor(px2)
因此,可以把原来的蚯蚓、切开后长的蚯蚓、切开后短的蚯蚓分别放入三个队列,每次只需取三个队列中front的最大数,就是当前蚯蚓的最大长度
另外为了统一,规定放进队列时的长度为这段蚯蚓在t=0时的长度,取出来时,只需增加相对应的取出时间,就能得到当前蚯蚓的实际长度。
我是用了两个队列和一个优先队列,当然也可以将输入元素放在一个新开的数组a,用sort对a进行排序,再放进队列1中
#include <bits/stdc++.h> using namespace std; typedef long long ll; ll n,m,q,u,v,t; priority_queue<ll> a1; queue<ll> a2,a3; //队列里存放蚯蚓第0秒长度 int main(){ ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); cin >> n >> m >> q >> u >> v >> t; double p = 1.0*u/v; for(int i=0;i<n;i++){ ll x; cin >> x; a1.push(x); } int cnt=0; for(int i=1;i<=m;i++){//i是当前时间 ll x,t1=-1e18,t2=-1e18,t3=-1e18; if(i==1){ x= a1.top();a1.pop(); } else{ if(!a1.empty()) t1 = a1.top(); if(!a2.empty()) t2 = a2.front(); if(!a3.empty()) t3 = a3.front(); if(t1>=t2 && t1>=t3){ a1.pop();x=t1+(i-1)*q;//转化成实际长度 } else if(t2>=t1 && t2>=t3){ a2.pop();x=t2+(i-1)*q;//转化成实际长度 } else if(t3>=t1 && t3>=t2){ a3.pop();x=t3+(i-1)*q;//转化成实际长度 } } ll x1 = floor(x*p);//切出来的一段长度 ll x2 = x-x1; //cout << "x x1 x2 " <<x << x1 << x2<< endl; if(x1>x2){ a2.push(x1-i*q);//a2放大的数,a3放小的数 a3.push(x2-i*q); } else{ a3.push(x1-i*q);//a2放大的数,a3放小的数 a2.push(x2-i*q); } if(i%t==0){ cnt++; cout << x ; if(cnt!=m/t) cout << " "; } } cout << "\n"; cnt=0; for(int i=1;i<=m+n;i++){ ll x,t1=-1e18,t2=-1e18,t3=-1e18; if(!a1.empty()) t1 = a1.top(); if(!a2.empty()) t2 = a2.front(); if(!a3.empty()) t3 = a3.front(); if(t1>=t2 && t1>=t3){ a1.pop();x=t1+m*q;//转化成实际长度 } else if(t2>=t1 && t2>=t3){ a2.pop();x=t2+m*q;//转化成实际长度 } else if(t3>=t1 && t3>=t2){ a3.pop();x=t3+m*q;//转化成实际长度 } if(i%t==0){ cout << x; if(cnt!=(m+n)/t) cout << " "; } } cout << "\n"; return 0; }