(ch1202) 蚯蚓

古城微笑少年丶 2022-10-02 12:47 40阅读 0赞

题目链接：[http://contest-hunter.org:83/contest/0x10「基本数据结构」例题/1202 蚯蚓][http_contest-hunter.org_83_contest_0x10_1202]

这个题真的是~~  
一言难尽 我真的无语了。  
先说一下这个题的基本思路吧。  
这个题目是个队列的题目。  
假定序列为  
a1 a2 a3 a4 a5 a6 a7 a8 a9  
并在此演示样例中 此序列是一个非降序的序列。

第一秒选a1 得到两个新的长度分别为 m1 = a1 \* u / v 和 m2 = a1 - m1;同时，队列中的其他元素的长度都增加了q。（**这里需要注意一下，对于一个序列来说，除了其中两个元素，其他元素都增加了q。那就可以用维持一个偏移量delta来表示整个数组的偏移量。而其他两个元素则需要减去q**）。所以，这里的m1 -= delta m2-= delta;

第二秒选a2 得到两个新的长度分别为 n1 = （a2 + delta） \* u / v - delta1和 n2 = a2 + delta- n1 - delta1; 注意，在执行第二秒的时候 m1 和 m2 的长度是要增加q的。  
所以，在第二秒执行完后，大致情况为  
m1 = a1 \* u / v - delta + delta1 m2 = a1 - m1 - delta + delta1;  
n1 = （a2 + delta） \* u / v - delta1 n2 = a2 + delta- n1 - delta1;  
通过公示的比较 易得  
m1 >= n1 m2 >= n2  
可得到结论，  
不仅从集合中取出的数是单调递减的，而且通过这个数所产生的两个数也都是分别单调递减的。  
如果这样的话，通过不断的产生数，我们是可以得到三个单调递减的序列的。我们在每次选择数的时候，选择这三个单调递减的序列中最大的数来切断。  
在具体实施的时候，还遇到了不少的问题。具体见代码

#include"stdio.h"
    #include"string.h"
    #include"queue"
    //#define p u/v
    #include"algorithm"
    using namespace std;
    typedef long long ll;
    
    priority_queue<ll> A;
    queue<ll> B,C;
    ll n,q,m,u,v,t;
    ll delta = 0;
    int main()
    {
        scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&q,&u,&v,&t);
        for(int i =  1; i <= n; i ++)
        {
            ll x;
            scanf("%lld",&x);
            A.push(x);
        }
        int cnt = 0;
        delta = 0;
        ll M = m;
        while(m --)
        {
             ll a = -10000000000,b = -10000000000,c = -10000000000;
            if(!A.empty())
                a = A.top();
            if(!B.empty())
                b = B.front();
            if(!C.empty())
                c = C.front();
            ll maxx;
            if(a >= b && a >= c)
            {
                A.pop();
                maxx = a;
            }
            else if(b >= a && b >= c)
            {
                B.pop();
                maxx = b;
            }
            else if(c >= a && c >= b)
            {
                C.pop();
                maxx =c;
            }
            cnt ++;
            if(cnt == t)
            {
                cnt = 0;
                printf("%lld ",maxx + delta);
            }
            maxx = maxx + delta;
            ll m1 = maxx * u / v;
            ll m2 = maxx - m1;
            delta += q;
            m1 -= delta; //这里应该是delta 不是q.因为在此次切断中，整个集合中的数应该加的是delta。
            m2 -= delta;
            B.push(m1);
            C.push(m2);
        }
        printf("\n");
        cnt = 0;
        for(int i = 1; i <= n + M; i ++)
        {
            ll a = -10000000000,b = -10000000000,c = -10000000000;
            //这里万分注意，一定要一个巨小的数。应该当B和C队列为空的时候，就不会赋到值。
            if(!A.empty())
                a = A.top();
            if(!B.empty())
                b = B.front();
            if(!C.empty())
                c = C.front();
            ll maxx = -1;
            if(a >= b && a >= c)
            {
                A.pop();
                maxx = a;
            }
            else if(b >= a && b >= c)
            {
                B.pop();
                maxx = b;
            }
            else if(c >= a && c >= b)
            {
                C.pop();
                maxx =c;
            }
            cnt ++;
            if(cnt == t)
            {
                cnt = 0;
                printf("%lld ",maxx + delta);
            }
        }
        printf("\n");
    }

[http_contest-hunter.org_83_contest_0x10_1202]: http://contest-hunter.org:83/contest/0x10%E3%80%8C%E5%9F%BA%E6%9C%AC%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%8D%E4%BE%8B%E9%A2%98/1202%20%E8%9A%AF%E8%9A%93