(CF1279C)Stack of Presents

发表于 分类于 ，

原题链接

思路:

对于压在栈 \(a\) 最底下的礼物 \(a_n\), 若 \(a_n\) 是所需要的礼物之一， 则可把数组 b 分为两部分:

  1. 对于交付时间在 \(a_n\) 前的礼物， 未排序并且已经拿走.

  2. 对于交付时间在 \(a_n\) 后的礼物， 已排序，花费时间为 1.

所以对于 \(a_n\), 设 \(a_n\) 为第 \(x\) 件取出的物品，则取出 \(a_n\) 所需要的时间为:

\[ 2(n-1-(x-1))+1 = 2(n-x)+1 \]

根据这个公式可以设计出算法:

对栈 \(a\) 从底向顶遍历，设第 \(o_i\) 个礼物为 \(a_i\), \(o_{min,i}\) 为区间 \((i,n]\) 中最小的 \(o_i\), 则取出 \(a_i\) 所需的时间:

\[ t_i = \begin{cases} 2(i-o_i)+1 &,\text{$o_i<o_{min,i}$} \\ 1 &,\text{$o_i>o_{min,i}$} \end{cases} \]

答案即为 \(t_i\) 之和.

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio>
#include <cstring>
const int Mn(100500);
int ax[Mn],tbx[Mn];    //ai与ai对应的oi(t取自transposition)
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d %d",&n,&m);
        memset(tbx,0,sizeof tbx);	//初始化
        for(int i(1);i<=n;++i)
            scanf("%d",ax+i);
        for(int i(1);i<=m;++i)
        {
            int x;
            scanf("%d",&x);
            tbx[x] = i;	//将ai与oi对应
        }
        long long ans(0);	//答案
        int mn(m+1);	//o{min,i}
        for(int i(n);i;--i)
        {
            if(tbx[ax[i]])	//若ai是所需礼物之一
            {
                if(tbx[ax[i]]<mn)	//case1
                    { mn=tbx[ax[i]]; ans+=2*(i-tbx[ax[i]])+1; }
                else	//case2
                    ++ans;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}