趴了一个小时想到了正解真TM开心
然后T3挂烂了
三个队列，一开始将所有数从大到小丢到第一个队列，之后每次从三个队列的首段取出最大的那个切了分别丢入二三队列。可以证明二三队列也一定是单调不增的。
常数优化很玄学
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <iostream> #include <cstdio> #include <queue> #include <cmath> #include <algorithm> using namespace std; typedef long long lol; int gi(){ int res=0,fh=1;char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); return fh*res; } const int MAXN=7000010; const int INF=2e9; int q[3][MAXN]; bool cmp(int x,int y){return x>y;} int main(){ int n=gi(),m=gi(),p=gi(),u=gi(),v=gi(),t=gi(); for(int i=1;i<=n;i++)q[0][i]=gi(); sort(q[0]+1,q[0]+n+1,cmp); int l[3]={1,1,1},r[3]={n,0,0},cnt=0;lol tp=0; for(int i=1;i<=m;i++){ int s[3];lol x; for(int i=0;i<3;i++) if(l[i]>r[i])s[i]=-INF; else s[i]=q[i][l[i]]; if(s[0]>=s[1]&&s[0]>=s[2])x=s[0]+tp,l[0]++; else if(s[1]>=s[2])x=s[1]+tp,l[1]++; else x=s[2]+tp,l[2]++; if(!(++cnt%t))printf("%lld ",x); lol A=u*x/v,B=x-A; tp+=p; q[1][++r[1]]=A-tp;q[2][++r[2]]=B-tp; } putchar('\n'); cnt=0; for(int i=1;i<=n+m;i++){ int s[3];lol x; for(int i=0;i<3;i++) if(l[i]>r[i])s[i]=-INF; else s[i]=q[i][l[i]]; if(s[0]>=s[1]&&s[0]>=s[2])x=s[0]+tp,l[0]++; else if(s[1]>=s[2])x=s[1]+tp,l[1]++; else x=s[2]+tp,l[2]++; if(!(++cnt%t))printf("%lld ",x); } return 0; } |