[NOIP 2016 D2 T2] 지렁이.

제목.
인터넷 에 다 있 으 니 스스로 찾 아 라.
풀다.
폭력 적
65 점 폭력: 우선 대기 열 을 사용 하고 시 뮬 레이 션, 복잡 도 O (m) log (n+m)) O ( m   l o g   (n + m) 코드 참조:

#include 
using namespace std;

#define R register

int n,m,q,t,nowtime;
double u,v,p;
struct QY
{
    int len,born;
    QY() {len=0,born=0;}
    int glen() {return len+(nowtime-born)*q;}
    friend bool operator < (const QY &x,const QY &y)
    {
        return x.len+(nowtime-x.born)*q < y.len+(nowtime-y.born)*q;
    }
};
priority_queue vector,less > Q;

int main()
{
    scanf("%d %d %d %lf %lf %d",&n,&m,&q,&u,&v,&t);
    p = u/v;
    for (R int i=1;i<=n;++i)
    {
        R int tmp;
        R QY tmp1;
        scanf("%d",&tmp);
        tmp1.len=tmp,tmp1.born=0;
        Q.push(tmp1);
    }
    for (nowtime=0; nowtimeif(!((nowtime+1)%t)) printf("%d ",tmp1.glen());
        Q.pop();
        R int len1=floor((double)tmp1.glen()*p),len2=tmp1.glen()-len1;
        ++ nowtime;
        R QY tmp2,tmp3;
        tmp2.len=len1,tmp3.len=len2,tmp2.born=tmp3.born=nowtime;
        Q.push(tmp2); Q.push(tmp3);
    }
    puts("");
    R int cnt=0;
    while(!Q.empty())
    {
        ++ cnt;
        R QY tmp1=Q.top();
        if(!(cnt%t)) printf("%d ",tmp1.glen());
        Q.pop();
    }
    return 0;
}

정 해
이 데 이 터 는 그래 픽 카드 log...너무 열악 하 다.다른 한 부 는 다른 대열 에 쑤 셔 넣 었 다.우 리 는 이 두 대열 도 단 조 롭 고 엄격하게 감소 하지 않 는 다 는 것 을 증명 할 수 있다.증명: 두 대열 이 대칭 성 을 가지 기 때문에 우 리 는 그 중의 하 나 를 증명 하면 된다.두 개의 선후 로 잘 린 지렁이 가 x, y x, y 인 데 그 중에서 x x 는 y 보다 먼저 잘 린 다.중간 과정 설정 t 시간 이 지 났 습 니 다.그러면 이 대열 에 넣 은 지렁이 는 선착순 길이 에 따라 각각 lenxp + tq, (leny + tq) p l e n x p + t q, (l e n y + t q) p (하 취 정 영향 이 크 지 않 음) 가 뚜렷 하 며, p ≤ 1 p ≤ 1, lenxp + tq ≤ lenyp + tqp l e n x p + t q ≤ l e n y p + t p + t q ≤ l e n y p + t q 를 베 는 선착순 으로 대열 에 넣 습 니 다.이 두 대열 은 마찬가지 로 단 조 를 유지한다.이렇게 해서 우 리 는 매번 세 개의 대열 에서 가장 큰 것 을 꺼 내 서 잘라 내 고 두 개의 대열 에 넣 으 면 복잡 도 는 선형 으로 변 한다.코드 는 다음 과 같 습 니 다. 심심 한 손 으로 작은 대기 열 템 플 릿 을 썼 습 니 다.

#include 
using namespace std;

#define R register
#define Maxn 100005
#define Maxm 7000005

int n,m,q,t;
struct QY 
{
    int len,born;
    QY(){len=0;born=0;}
    inline int getlen(R int tim){return len+(tim-born)*q;}
};
inline bool cmp(R QY xx,R QY yy) {return xx.len>yy.len;}
struct Que
{
    QY q[Maxm];
    int head,tail;
    Que(){memset(q,0,sizeof q);head=1,tail=0;}
    inline QY front() {return q[head];}
    inline void pop() {++head;}
    inline void push(R QY val) {q[++tail]=val;}
    inline bool empty() {return head > tail;}  
}s[3];
double u,v,p; 
int dmax(R int tim)
{
    R int maxx=-1,maxi=-1;
    for(R int i=0;i<3;++i) 
    {
        if(s[i].empty()) continue;
        R int tmp=s[i].front().getlen(tim);
        if(tmp > maxx) maxx=tmp,maxi=i;
    }
    return maxi;
}
int main()
{
    scanf("%d %d %d %lf %lf %d",&n,&m,&q,&u,&v,&t);
    p = u/v;
    for (R int i=1;i<=n;++i) 
    {
        R QY tmp; 
        scanf("%d",&tmp.len);
        s[0].push(tmp);
    }
    sort(s[0].q+1,s[0].q+n+1,cmp);
    for (R int i=1;i<=m;++i)
    {
        R int Maxq=dmax(i-1),tmp=s[Maxq].front().getlen(i-1);
        if(!(i%t)) printf("%d ",tmp);
        s[Maxq].pop();
        R int len1=floor(double(tmp*p)),len2=tmp-len1;
        R QY tmp1;
        tmp1.len=len1;tmp1.born=i;s[1].push(tmp1);
        tmp1.len=len2;s[2].push(tmp1);
    }
    puts("");
    for(R int i=1;i<=n+m;++i)
    {
        R int Maxq=dmax(m),tmp=s[Maxq].front().getlen(m);
        if(!(i%t)) printf("%d ",tmp);
        s[Maxq].pop(); 
    }
    return 0;
}