[NOIP2016]蚯蚓

第一行包含六个整数 n，m，q，u，v，t，其中：n，m，q 的意义见「题目描述」；u，v，t 均为正整数，你需要自己计算 $p = \frac{u}{v}$ （保证 0 < u < v）；t 是输出参数，其含义将会在「输出描述」中解释。
第二行包含 n 个非负整数，为 a₁, a₂, ..., a_n，即初始时 n 只蚯蚓的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。
保证 1 ≤ n ≤ 10⁵，0 < m < 7 x 10⁶，0 < u < v < 10⁹，0 ≤ q ≤ 200，1 < t < 71，0 < a_i < 10⁸。

第一行输出 $\lfloor \frac{m}{t} \rfloor$ 个整数，按时间顺序，依次输出第 t 秒，第 2t 秒，第 3t 秒 …… 被切断蚯蚓（在被切断前）的长度。
第二行输出 $\lfloor \frac{(n+m)}{t} \rfloor$ 个整数，输出 m 秒后蚯蚓的长度；需要按从大到小的顺序，依次输出排名第 t，第 2t，第 3t …… 的长度。
同一行中相邻的两个数之间，恰好用一个空格隔开。即使某一行没有任何数需要输出，你也应输出一个空行。
请阅读样例来更好地理解这个格式。

C++14(g++5.4) 解法, 执行用时: 362ms, 内存消耗: 31876K, 提交时间: 2020-03-15 11:00:31

#include <bits/stdc++.h>
using namespace std;
priority_queue<int>q1;
queue<int>q2,q3;
int n,m,l,q,u,v,t;
int maxlen(int t)
{
    int x1=-1,x2=-1,x3=-1;
    if(!q1.empty()) x1=q1.top()+t*q;
    if(!q2.empty()) x2=q2.front()+t*q;
    if(!q3.empty()) x3=q3.front()+t*q;
    if(x1>=x2&&x1>=x3){q1.pop();return x1;}
    else if(x2>=x1&&x2>=x3){q2.pop();return x2;}
    else{q3.pop();return x3;}
}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
    for(int i=1;i<=n;i++) scanf("%d",&l),q1.push(l);
    for(int i=1;i<=m;i++)
    {
        long long len=maxlen(i-1),t1=len*u/v,t2=len-t1;
        q2.push(t1-i*q);q3.push(t2-i*q);
        if(i%t==0) printf("%d ",len);
    }
    puts("");
    for(int i=1,len=maxlen(m);i<=m+n;i++,len=maxlen(m)) if(i%t==0) printf("%d ",len);
}

C++(clang++ 11.0.1) 解法, 执行用时: 289ms, 内存消耗: 32420K, 提交时间: 2023-07-04 13:16:42

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	ll n,m,q,u,v,t,i,j,k,d[100005];
	queue<int>a[3];
	cin>>n>>m>>q>>u>>v>>t;
	double tt=u*1.0/v;
	for(i=0;i<n;i++)
	cin>>d[i];
	sort(d,d+n);
	for(i=n-1;i>=0;i--)
	a[0].push(d[i]);
	for(i=1;i<=m;i++){
		ll mx=-1e18,pos,x1,x2;
		for(j=0;j<=2;j++){
			if(!a[j].empty()&&a[j].front()>mx)
			mx=a[j].front(),pos=j;
		}
		a[pos].pop();
		mx+=(i-1)*q;
		if(i%t==0) cout<<mx<<' ';
		x1=mx*tt;
		x2=mx-x1;
		a[1].push(x1-i*q),a[2].push(x2-i*q);
	}
	cout<<endl;
	for(i=1;i<=m+n;i++){
		ll mx=-1e18,pos;
		for(j=0;j<=2;j++){
			if(!a[j].empty()&&a[j].front()>mx)
			mx=a[j].front(),pos=j;
		}
		a[pos].pop();
		if(i%t==0)
		cout<<mx+m*q<<' ';
	}
	cout<<endl;
	
	
	
}

详情