NOIP 2016 蚯蚓(洛谷 P2827)

时间:2023-01-01 19:32:05

题目描述

本题中,我们将用符号[c]表示对c向下取整,例如:[3.0」= [3.1」=[3.9」=3。
蛐蛐国最近蚯蚓成灾了!隔壁跳蚤国的跳蚤也拿蚯蚓们没办法,蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有n只蚯蚓(n为正整数)。每只蚯蚓拥有长度,我们设第i只蚯蚓的长度为a_i(i=1,2,…,n),并保证所有的长度都是非负整数(即:可能存在长度为0的蚯蚓)。
每一秒,神刀手会在所有的蚯蚓中,准确地找到最长的那一只(如有多个则任选一个)将其切成两半。神刀手切开蚯蚓的位置由常数p(是满足0

/*
这道题目网上有优先队列的做法,但是好像会TLE,我没试,
那天和包子学长聊天,忘了怎么的聊到NOIP,他说有一道数据结构题,
当时我就蒙蔽了,他还说能用优先队列优化,大概就是这道吧,
虽然超时但是部分分已经相当可观了,这或许就是他出一等的原因吧
*/
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
const int maxm = 1e7 + 10;
int n,m,q,u,v,t;
int a,b,c,t1,t2,t3,h4,h2,h3;
int q1[maxn],q2[maxm],q3[maxm],q4[maxn+maxm];
bool Cmp(int x,int y){return x>y;}
int Pop_Head(int k){
int x=q1[t1]+q*k;
int y=q2[t2]+q*(k-t2-1);
int z=q3[t3]+q*(k-t3-1);
if(n>t1&&x>=y&&x>=z) {t1++;return x;}
else if(h2>t2&&y>=z) {t2++;return y;}
else if(h3>t3) {t3++;return z;}
else return -1;
}
int main(){
scanf("%d%d%d%d%d%d",&n,&m,&q,&u,&v,&t);
for(int i=0;i<n;i++) scanf("%d",&q1[i]);
sort(q1,q1+n,Cmp);
for(int i=0;i<m;i++){
a=Pop_Head(i);
if((i+1)%t==0) printf("%d ",a);
b=1ll*a*u/v;c=a-b;
q2[h2++]=b;q3[h3++]=c;
}
while(q4[h4]=Pop_Head(m),q4[h4]!=-1) h4++;
cout<<endl;
for(int i=t-1;i<h4;i+=t) printf("%d ",q4[i]);
return 0;
}