简答题 偏难
#23306

贪吃蛇(snakes) 【题目描述】 草原上有 n 条蛇,编号分别为 1,2, ⋯ , n。初始时每条蛇有一个体力值ai,我们称编号为 x 的蛇实力比编号为 y…

贪吃蛇(snakes)

【题目描述】

草原上有 n 条蛇,编号分别为 1,2, ⋯ , n。初始时每条蛇有一个体力值ai,我们称编号为 x 的蛇实力比编号为 y 的蛇强当且仅当它们当前的体力值满足 ax > ay,或者 ax = ay 且 x > y。

接下来这些蛇将进行决斗,决斗将持续若干轮,每一轮实力最强的蛇拥有选择权,可以选择吃或者不吃掉实力最弱的蛇:

1. 如果选择吃,那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值,实力最弱的蛇被吃掉,退出接下来的决斗。之后开始下一轮决斗。

2. 如果选择不吃,决斗立刻结束。

每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇(显然,蛇不会选择吃自己)。

现在假设每条蛇都足够聪明,请你求出决斗结束后会剩几条蛇。

本题有多组数据,对于第一组数据,每条蛇体力会全部由输入给出,之后的每一组数据,会相对于上一组的数据,修改一部分蛇的体力作为新的输入。

【输入格式】

输入文件名为 snakes.in。

第一行一个正整数 T,表示数据组数。

接下来有 T 组数据,对于第 1 组数据,第一行一个正整数 n,第二行 n个非负整数表示 ai。

对于第 2 组到第 T 组数据,每组数据:

第一行第一个非负整数 k 表示体力修改的蛇的个数。

第二行 2k 个整数,每两个整数组成一个二元组 (x, y),表示依次将 ax的值改为 y。一个位置可能被修改多次,以最后一次修改为准。

【输出格式】

输入文件名为 snakes.out。

输出 T 行,每行一个整数表示最终存活的蛇的条数。

【样例 1 输入】

2

3

11 14 14 

3

1 5 2 6 3 25

【样例 1 输出】

3

1

【样例 1 解释】

第一组数据,第一轮中 3 号蛇最强,1 号蛇最弱。若 3 号蛇选择吃,那么它将在第二轮被 2 号蛇吃掉。因此 3 号蛇第一轮选择不吃,3 条蛇都将存活。

对于第二组数据,3 条蛇体力变为 5,6,25。第一轮中 3 号蛇最强,1 号蛇最弱,若它选择吃,那么 3 号蛇体力值变为 20,在第二轮中依然是最强蛇并能吃掉 2 号蛇,因此 3 号蛇会选择两轮都吃,最终只有 1 条蛇存活。

【样例 2 输入】

2

5

13 31 33 39 42 

5

1 7 2 10 3 24 4 48 5 50

【样例 2 输出】

5

3

【数据范围与提示】

对于 20%的数据:n = 3。

对于 40%的数据:n ≤ 10。

对于 55%的数据:n ≤ 2000。

对于 70%的数据:n ≤ 5 × 10^4。

对于 100%的数据:3 ≤ n ≤ 10^6,1 ≤ T ≤ 10,0 ≤ k ≤ 10^5,0 ≤ ai, y ≤10^9。

保证每组数据(包括所有修改完成后的)的 ai 以不降顺序排列。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include&lt;iostream&gt;</p><p style="text-align: left;">#include&lt;cstdio&gt;</p><p style="text-align: left;">#include&lt;queue&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int N=1e6+100,INF=1e9;</p><p style="text-align: left;">struct Node</p><p style="text-align: left;">{</p><p style="text-align: left;">    int val,num;</p><p style="text-align: left;">    #define val(i) a[i].val</p><p style="text-align: left;">    #define num(i) a[i].num</p><p style="text-align: left;">    bool operator &lt; (const Node y)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        return val==y.val?num&lt;y.num:val&lt;y.val;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    bool operator == (const Node y)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        return val==y.val &amp;&amp; num==y.num;</p><p style="text-align: left;">    }</p><p style="text-align: left;">}a[N];</p><p style="text-align: left;">int T,n,k,ph,pb;</p><p style="text-align: left;">queue&lt;Node&gt; q;</p><p style="text-align: left;">Node blank={0,0},black={INF,INF};</p><p style="text-align: left;">Node Max(Node x,Node y)</p><p style="text-align: left;">{</p><p style="text-align: left;">    return (x&lt;y)?y:x;</p><p style="text-align: left;">}</p><p style="text-align: left;">Node Min(Node x,Node y)</p><p style="text-align: left;">{</p><p style="text-align: left;">    return (x&lt;y)?x:y;</p><p style="text-align: left;">}</p><p style="text-align: left;">bool query(Node la)</p><p style="text-align: left;">{</p><p style="text-align: left;">    int cnt=0;</p><p style="text-align: left;">    Node bk=Min(pb&lt;ph?a[pb+1]:black,q.size()?q.back():black);</p><p style="text-align: left;">    while(1)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        Node hd=Max(pb&lt;ph?a[ph]:blank,q.size()?q.front():blank);</p><p style="text-align: left;">        if(a[ph]==hd)</p><p style="text-align: left;">            ph--;</p><p style="text-align: left;">        else</p><p style="text-align: left;">            if(q.size())</p><p style="text-align: left;">                q.pop();</p><p style="text-align: left;">        if(hd==bk)</p><p style="text-align: left;">            break;</p><p style="text-align: left;">        hd.val-=la.val;</p><p style="text-align: left;">        if(bk&lt;hd)</p><p style="text-align: left;">            break;</p><p style="text-align: left;">        la=hd;cnt++;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return cnt&amp;1;</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;">    scanf("%d",&amp;T);</p><p style="text-align: left;">    for(int i=1;i&lt;=T;i++)</p><p style="text-align: left;">    {</p><p style="text-align: left;">        if(i==1)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            scanf("%d",&amp;n);</p><p style="text-align: left;">            for(int j=1;j&lt;=n;j++)</p><p style="text-align: left;">                scanf("%d",&amp;val(j)),num(j)=j;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        else</p><p style="text-align: left;">        {</p><p style="text-align: left;">            scanf("%d",&amp;k);</p><p style="text-align: left;">            for(int j=1,x,y;j&lt;=k;j++)</p><p style="text-align: left;">            {</p><p style="text-align: left;">                scanf("%d%d",&amp;x,&amp;y);</p><p style="text-align: left;">                val(x)=y;</p><p style="text-align: left;">            }</p><p style="text-align: left;">        }</p><p style="text-align: left;">        ph=n,pb=1;</p><p style="text-align: left;">        while(q.size())</p><p style="text-align: left;">            q.pop();</p><p style="text-align: left;">        while(pb&lt;=ph)</p><p style="text-align: left;">        {</p><p style="text-align: left;">            Node x=Max((ph&gt;pb)?a[ph]:blank,q.size()?q.front():blank);</p><p style="text-align: left;">            if(a[ph]==x)</p><p style="text-align: left;">                ph--;</p><p style="text-align: left;">            else</p><p style="text-align: left;">                q.pop();</p><p style="text-align: left;">            x.val-=val(pb);</p><p style="text-align: left;">            if(x&lt;a[pb+1] &amp;&amp; n-pb&gt;1)</p><p style="text-align: left;">            {</p><p style="text-align: left;">                if(query(x))</p><p style="text-align: left;">                    pb++;</p><p style="text-align: left;">                break;</p><p style="text-align: left;">            }</p><p style="text-align: left;">            q.push(x);pb++;</p><p style="text-align: left;">        }</p><p style="text-align: left;">        printf("%d\n",n-pb+1);</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。