AcWing 133. 蚯蚓

AcWing 133. 蚯蚓
做起来很难的一道队列题，容易踩到优先队列的坑里（超时）。需要对其进行优化。

思路

1. 这里数构分为 $3$ 个队列，$q1$ 初始队列、$q2$ 左半段的队列、$q3$ 右半段的队列。

2. 将 $q1$ 大到小排序。

3. 那么蚯蚓分开后的两段肯定是一大一小或一样大，不管怎么样蚯蚓分开后并插入左右队列 $q2$、$q3$ 一定是单调递减的（因为初始队列是 $q1$ 单调递减）。所以接下来，我们要找出最大的蚯蚓来分就容易了，直接枚举每个队列的头即可。

4. 因为分开蚯蚓后其他蚯蚓长度会 $+q$ ，所以我们可以已相对大小 $delta$ 来看待。（具体看代码）

至此时间复杂度 $O(n+m)$ ，就比优先队列做法 $O(mlogm)$ 高效了。

#include<iostream>
#include<algorithm>
#define int long long 
using namespace std;
const int N = 100010, M = 7000010;
int q1[N],q2[M],q3[M];
int h1,h2,h3,t1,t2,t3,delta;

bool cmp(const int &a,const int &b) {
    
	return a > b;
}

int get_max(){
    
	int res = -0x3f3f3f3f;
	
	if(h1 <= t1) res = max(res,q1[h1]);
	if(h2 <= t2) res = max(res,q2[h2]);
	if(h3 <= t3) res = max(res,q3[h3]);
	
	if(h1 <= t1 && res == q1[h1]) h1++;
	else if(h2 <= t2 && res == q2[h2]) h2++;
	else if(h3 <= t3 && res == q3[h3]) h3++;
	
	return res;
}

signed main(){
    
    cin.tie(0)->sync_with_stdio(false);
    cout.tie(0);
    int n,m,q,u,v,t;
    cin>>n>>m>>q>>u>>v>>t;
	double p = 1.0*u/v;
    for(int i = 0; i < n; i++) cin>>q1[i];
    sort(q1,q1 + n, cmp);
	t1 = n-1; t2 = t3 = -1; delta = 0; 
	
    for(int i = 1; i <= m; i++){
    
    	int x = get_max();
		x += delta; 
		if(i % t == 0) cout<<x<<' ';
		int l = (int)(p*x), r = x-l;
		delta += q;
		q2[++t2] = l - delta;
		q3[++t3] = r - delta;
	}
	
	cout<<'\n';
	
	for(int i = 1; i <= n+m; i++){
    
		int x = get_max();
		if(i % t == 0) cout<<x+delta<<' ';
	}	
	
	return 0;   
}