【每日一题】蚯蚓 题解

Description

Solution

难点在于题目太长了，输出也很麻烦。需要注意到 , 用优先队列每次找最大值显然是不可行的，需要寻找 的做法。对于一个数字 ，如果按照题目将它分成 和 , 如果 , 那么满足 和
基于以上性质，可以开三个队列，分别有：

• 原来的蚯蚓
• 分割出来的蚯蚓
• 分割出来的蚯蚓

那么只要原来的蚯蚓具有单调性，每次只需要找这三个队列的最大值即可
至于每次都要增加的长度，我们可以先不加上，等到取出来的时候在加 , 放回去的时候注意要减去

Code

#pragma GCC optimize(3)
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 2e5 + 5;
const int mod = 1e9 + 7;

queue<ll> q[3];
ll a[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  ll n, m, u, v, qq, t; cin >> n >> m >> qq >> u >> v >> t;
  for(int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + 1 + n);
  for(int i = n; i >= 1; i--) q[0].push(a[i]);
  for(int i = 1; i <= m; i++) {
    ll maxz = -1e18, pos = -1;
    for(int j = 0; j < 3; j++) {
      if(q[j].size() && q[j].front() > maxz) {
        maxz = q[j].front();
        pos = j;
      }
    }
    q[pos].pop();
    maxz += (i - 1) * qq; 
    ll x = maxz * u / v, y = maxz - x;
    if((i % t == 0)) cout << maxz << ' ';
    q[1].push(x - i * qq), q[2].push(y - i * qq);
  }
  cout << "\n";
  int cnt = 1;
  while(q[0].size() || q[1].size() || q[2].size()) {
    ll p = -1e18, pos = -1;
    for(int j = 0; j < 3; j++) {
      if(q[j].size() && q[j].front() > p) {
        pos = j;
        p = q[j].front();
      }
    }
    q[pos].pop();
    if(cnt % t == 0) {
      cout << p + m * qq << ' ';
    }
    cnt++;
  }
  cout << "\n";
  return 0;
}