题解 P2827 【蚯蚓】

林志杰 · 2017-11-07 20:19:01 · 题解

纯模拟，我们用三个队列，第一个存原始队列（从大到小排序），第二个存切完后较长的那个子蚯蚓，第三个存切完后较短的那个子蚯蚓。那么可以始终保持三个队列都是严格递减的。

每次从三个队列中选出最长的那个蚯蚓，切完后分别压入q1,q2，一直模拟即可。

//#include<math.h>
//double ceil(double x) //向上取整
//double floor(double x) //向下取整
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define R read()
#define re register
using namespace std;
const int maxn = 1e7;
int n,m,q,u,v,t;
int q0[maxn],h0=1,t0=0,q1[maxn],h1=1,t1=0,q2[maxn],h2=1,t2=0;
int O1,O2;
double p;
bool cmp(int x,int y)
{
    return x > y;
}
inline int read();
int main()
{
    n = R;m = R;q = R;u = R;v = R;t = R;
    for(re int i=1;i<=n;i++) {
        q0[i] = R;
        q0[i] += m*q;//先把蚯蚓可能长的长度加上，拿出来时再把多算的部分除去 
    }
    sort(q0+1,q0+n+1,cmp);
    t0 = n;p = (u*1.0)/(v*1.0);
    O1 = m/t;O2 = (n+m)/t;//两行分别应该输出的数的数量 
    for(re int i=1,a=0,b=0,c=0,x1,x2,d;i<=m;i++) {//模拟切割 
        a = 0;b = 0;c = 0;
        if(h0<=t0) a = q0[h0];
        if(h1<=t1) b = q1[h1];
        if(h2<=t2) c = q2[h2];
        d = max(a,max(b,c));//选出最长的 
        if(a == d && h0<=t0) ++h0;
        else if(b == d && h1<=t1) ++h1;
        else ++h2;//把选的那条蚯蚓弹出队列 
        d -= (m-i+1)*q;
        if(i%t == 0 && O1) {
            printf("%d ",d);
            --O1;

}//输出

        x1 = floor(p*(1.0*d));
        x2 = d - x1;
        if(x1 > x2) {
            q1[++t1] = x1+(m-i)*q;
            q2[++t2] = x2+(m-i)*q;
        }
        else {
            q1[++t1] = x2+(m-i)*q;
            q2[++t2] = x1+(m-i)*q;

}//分别压入另外两个队列

    }
    cout<<endl;
    int i=0,a,b,c,d;
    while(O2) {//判断剩下的长度，过程相似 
        ++i;
        a = 0;b = 0;c = 0;
        if(h0<=t0) a = q0[h0];
        if(h1<=t1) b = q1[h1];
        if(h2<=t2) c = q2[h2];
        d = max(a,max(b,c));
        if(i%t == 0 && O2) {
            printf("%d ",d);
            --O2;
        }
        if(a == d && h0<=t0) ++h0;
        else if(b == d && h1<=t1) ++h1;
        else ++h2;
    }
    return 0;
}
inline int read()
{
    int w=1,x=0;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') w = -1;
        ch = getchar();
    }
    while(ch <= '9' && ch >= '0') {
        x = (x<<1) + (x<<3) + ch - '0';
        ch = getchar();
    }
    return x*w;
}