这个，题解见我的另一个blog：NOIP2016Day2总结
注意题目中本身蕴含的单调性，与合并果子的做法略微相似，利用决策的单调性
1 /******************** 2 User:Mandy 3 Language:c++ 4 Problem:D2T2 earthworm 5 ********************/ 6 7 #include<bits/stdc++.h> 8 using namespace std; 9 10 const int maxn=1e5+5; 11 const int maxm=7e6+5; 12 const int inf=2100000000; 13 14 int n,m,q,u,v,t; 15 int l1,r1,l2,r2,l3,r3; 16 int q1[maxn],q2[maxm<<1],q3[maxm<<1]; 17 double p; 18 19 template<typename T>inline void read(T &x) 20 { 21 x=0;bool f=0;char c=getchar(); 22 while(c<'0'||c>'9') {f|=(c=='-');c=getchar();} 23 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+(c^48);c=getchar();} 24 if(f)x=-x; 25 } 26 27 template<typename T>void putch(const T x) 28 { 29 if(x>9) putch(x/10); 30 putchar((x%10)|48); 31 } 32 33 template<typename T>void put(const T x) 34 { 35 if(x<0) putchar('-'),putch(-x); 36 else putch(x); 37 } 38 39 void docu() 40 { 41 freopen("earthworm.txt","r",stdin); 42 } 43 44 bool cmp(int a,int b) 45 { 46 return a>b; 47 } 48 49 void readdata() 50 { 51 read(n);read(m);read(q);read(u);read(v);read(t); 52 p=(double)u/v; 53 for(int i=0;i<n;++i) read(q1[i]); 54 sort(q1,q1+n,cmp); 55 } 56 57 void work() 58 { 59 l2=r2=0;l3=r3=0; 60 l1=0;r1=n; 61 for(int i=1;i<=m;++i) 62 { 63 int x=-inf,x1,x2,judge=0; 64 if(l1!=r1) {x=q1[l1];judge=1;} 65 if(l2!=r2&&q2[l2]>x) {x=q2[l2];judge=2;} 66 if(l3!=r3&&q3[l3]>x) {x=q3[l3];judge=3;} 67 switch(judge){ 68 case 1:{++l1;break;} 69 case 2:{++l2;break;} 70 default:{++l3;break;} 71 } 72 x+=(i-1)*q; 73 x1=floor(x*p);x2=x-x1; 74 x1-=q*i;x2-=q*i; 75 q2[r2++]=min(x1,x2); 76 q3[r3++]=max(x1,x2); 77 if(i%t==0) {put(x);putchar(' ');} 78 } 79 putchar(' '); 80 int i=0; 81 while(l1!=r1||l2!=r2||l3!=r3) 82 { 83 ++i; 84 int x=-inf,judge=0; 85 if(l1!=r1) {x=q1[l1];judge=1;} 86 if(l2!=r2&&q2[l2]>x) {x=q2[l2];judge=2;} 87 if(l3!=r3&&q3[l3]>x) {x=q3[l3];judge=3;} 88 switch(judge){ 89 case 1:{++l1;break;} 90 case 2:{++l2;break;} 91 default:{++l3;break;} 92 } 93 if(i%t==0) {put(x+q*m);putchar(' ');} 94 } 95 putchar(' '); 96 } 97 98 int main() 99 { 100 // docu(); 101 readdata(); 102 work(); 103 return 0; 104 }