首页 > 其他 > 详细

p1456

时间:2018-10-06 10:14:48      阅读:126      评论:0      收藏:0      [点我收藏+]

可能这是我的巅峰了吧.

技术分享图片

技术分享图片

技术分享图片

技术分享图片

这题什么意思呢.

有一堆数,m秒内总选取最大的一个下手:把它分成?x*u/v?和x-?x*u/v?.其他的都增长q;求每秒内的最大数和最后的所有剩下的数.

(本题可以上一个优先队列很快的就水了,但是oj不允许哇.)

考虑不增长的时候怎么做?我们来开三个队列.先把最开始的长度排序后放入第一个队列里,找到三个队头的最大值分一下后就分别扔到两个队列里.然后再找最大值...

考虑为什么这样做是正确的.

这是因为两个队列是历史上最大值分下来的,只要你放的顺序不变,先进入的一定是更大值分得的,比后进入的大.这样子三个队列内部都是递减的,而且二三个队列总大于新的最大值分到的.

输出的时候就还是不断的对三个队列找最大值后输出.

 

考虑增长的时候怎么做.

可以利用差分的思想,或者说利用时间戳?我们记录每一个数分的时候的时间,也就是刚开始全部为1,23队列是循环的时候的i值.这样求值的时候只需把队列中的值加上q*(i-t)就好.然后分了之后重新记时间.

输出的时候同理.

就很开心的写了一个重载运算符.代码瞬间简介(

//全代码不敢用.size()
int i,t;
int n,m,q,T;
double u,v;
int now,e1,e2,e3;

struct aba:queue<int>
{
};
int operator + (const aba &a,const aba &t)
{
    if(a.empty())//如果为空
        return -1000000;//交的时候没这么小,还好没卡我
    return a.front()+q*(i-t.front());//这是为什么下面输出的时候让i=m+1而让一个n控制循环的原因
}
aba a1;
aba a2;
aba a3;
aba t1;
aba t2;
aba t3;
aba ans;
inline int maxx()
{
    e1=a1+t1;e2=a2+t2;e3=a3+t3;
    if(e1>=e2&&e1>=e3)
    {
        a1.pop();t1.pop();
        return e1;
    }
    if(e2>=e1&&e2>=e3)
    {
        a2.pop();
        t2.pop();
        return e2;
    }
    a3.pop();t3.pop();
    return e3;
}
int o[1000000];
inline bool Orz(int a,int b)
{
    return a>b;
}
int main()
{
    n=read(),m=read(),q=read(),u=read(),v=read(),T=read();
    for(i=1;i<=n;i++)
        o[i]=read();
    sort(o+1,o+1+n,Orz);
    for(i=1;i<=n;i++){
        a1.push(o[i]);
        t1.push(1);
    }
    
    for(i=1;i<=m;i++){
        now=maxx();
        if(i%T==0)
            cout<<now<< ;
        a2.push(int(now*u/v)-q);
        t2.push(i);
        a3.push(now-int(now*u/v)-q);//注意取整的位置
        t3.push(i);
    }
    cout<<endl;
    i=m+1;
    for(n=1;!a1.empty()|| !a2.empty()|| !a3.empty();n++){
        now=maxx();
        if(n%T==0)
            cout<<now<< ;
    }
}

 

p1456

原文:https://www.cnblogs.com/qywyt/p/9746532.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!