使用优先队列会超时,因为优先队列的内部实现是小根堆或大根堆。并不是O(N)的时间复杂度。
在本题当中可以使用三个队列,一个原始序列排序好的队列,一个切完后左边蚯蚓的队列,一个切完后右边蚯蚓的队列。这样只需要每次比较队首的蚯蚓长度就可以得到刽子手需要去砍的蚯蚓。
然后本题的输出比较麻烦,需要输出在砍的某个蚯蚓之前的长度和最终所有蚯蚓的长度,本题解采用假设当前蚯蚓从一开始就存在,然后在最终加上时间即可。
那么就需要在出对的时候将时间增长的加上,在如果的时候再减去。
#include <bits/stdc++.h> typedef long long ll; using namespace std; const int maxn = 1e5+10; queue<ll> qu[3]; ll a[maxn]; int main() { ll n, m, q, u, v, t; ll time = 1; cin>>n>>m>>q>>u>>v>>t; for (int i=0;i<n;i++) { scanf("%lld", a+i); } sort(a, a+n, greater<ll>()); for (int i=0;i<n;i++) { qu[0].push(a[i]); } while (time<=m) { int pos = 0; int max = INT_MIN; for (int i=0;i<3;i++) { if (!qu[i].empty()&&qu[i].front()>max) { max = qu[i].front(); pos = i; } } int len = qu[pos].front()+(time-1)*q; qu[pos].pop(); if (time%t==0) printf("%lld ",len); int l = len*((double) u/v); int r = len-l; qu[1].push(l-q*time);qu[2].push(r-q*time); time++; } cout<<endl; int number = 1; while (qu[0].size()||qu[1].size()||qu[2].size()) { int pos = 0; int max = INT_MIN; for (int i=0;i<3;i++) { if (!qu[i].empty()&&qu[i].front()>max) { max = qu[i].front(); pos = i; } } if (number%t==0) { printf("%lld ", qu[pos].front()+m*q); } qu[pos].pop(); number++; } return 0; }