题解：P9499 「RiOI-2」change

· · 题解

0.前言：

一道神奇小贪心。题解区的贪心题解感觉都重在讲做法，让人不理解贪的过程，所以写一篇，部分贪心的证明过程可能比较简略，详细可以看其它题解。

注意：本题解的 x 数组下标为 2\sim n，即 x_i 表示第 i-1 个元素合成到第 i 个元素所需的数量，与题面略有差异。

1.思路：

首先需要一个记录第 i 个物品价值为 v_{i,j} 的数量有 c_{i,j} 个的数组，即数组中的每个元素为一个二元组。注意：这里的 v_{i,j} 不仅仅可能是第 i 个物品的价值，也可能有前面的物品合成到第 i 个物品所需的价值。

举个例子：当前第 i 个物品价值为 5，个数为 3，那么数组中应该有 (5,3) 这个二元组。如果前面的某 x 个元素的总价值为 4，合成了 1 个第 i 个物品，那么数组中也应该有 (4,1) 这个二元组。

接着按编号从小到大枚举物品，对于第 i 个物品我们考虑用第 i-1 个物品合成它。对记录第 i-1 个物品情况的数组，将数组按照 v 从小到大排序。接着每 x_i 个元素合成第 i 个元素。注意：如果合成出来的元素的 v 小于第 i 个元素本身的价值 v_i，那么就相当于我们以一个小代价获得了更大价值的物品。我们会加上这个利润，并且在接下来的合成过程中将这个物品的价值认为是 v_i。

举个例子：第 i-1 个元素的二元组中有 (4,2),(5,3),(6,2),(7,1)，x_i=3，v_i=15，c_i=4。首先对二元组进行排序，这是已经排好序的结果。显然第 i 个元素对应的二元组中有 (15,4)，接着每 x_i 个去合成。那么第一个合成的二元组就是 (13,1)（4+4+5=13），但是因为 13\lt 15，所以将 13 变为 15，减去 13\times 1 的价值，(15,4) 变成 (15,5)。接着又合成了 (16,1)，（5+5+6=16），但是 16\gt 15，所以保留下来。还剩下两个无法合成，可以直接扔掉。最后加上 (15,4) 的价值 75 即可。

2.细节：

首先我们可以优化一下对于二元组的排序。显然合成出来的二元组的 v 是逐渐增大的。所以我们用一个 v 单调递减的栈来记录二元组。合成出来的结果用一个临时栈来记录，合成完再把临时栈赋值给原来的栈。但是临时栈中的元素是单调递增的，所以要倒着赋值。这样同时我们不需要对每个元素都开一个栈，用这种类似滚动数组的方式就好了。（因为每个元素只跟上一个有关系。）

接着考虑时间复杂度问题。对于 x_i\gt 1 的情况，每次合成的数量都至少比原来减半，所以是 \mathcal O(n\log n) 的、对于 x_i=1 的情况，不需要进行合成，因为单独一个 i-1 就是 i，只不过二元组中价值 v\lt v_i，将 v=v_i 即可，和上面的没有区别。

最后，当合成时遇到了合成的价值大于所有物品的最大值，那么这个合成出来的结果肯定是不好的，直接不要了。并且后面的合成得到的只会更大，直接退出即可。

3.AC code：

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
const int mod=998244353;
const lll one=1;
ll tid,t,n,v[200005],c[200005],x[200005];
lll st_v[200005],st_c[200005],top,ans;
lll tmp_v[200005],tmp_c[200005],tmp_top;
int main(){
    cin>>tid>>t;
    while(t--){
        scanf("%lld",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&v[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%lld",&c[i]);
        }
        for(int i=2;i<=n;i++){
            scanf("%lld",&x[i]);
        }
        top=0;
        st_v[++top]=v[1];
        st_c[top]=c[1];//将第一个元素的二元组放进去
        ans=one*v[1]*c[1];//贡献
        for(int i=2;i<=n;i++){
            if(x[i]>1){
                lll sumv=0,sumc=0;
                tmp_top=0;
                while(top){
                    lll vv=st_v[top],cc=st_c[top];
                    top--;
                    if(sumc>0){
                        lll w=min(x[i]-sumc,cc);
                        sumc+=w;
                        sumv+=vv*w;
                        cc-=w;
                        if(sumv>1e10) break;
                        if(sumc==x[i]){
                            tmp_v[++tmp_top]=sumv;
                            tmp_c[tmp_top]=1;
                            sumv=sumc=0;
                        }
                        else continue;
                    }
                    if(vv*x[i]>1e10) break;
                    tmp_v[++tmp_top]=vv*x[i];//这里某个合成的结果全部来自一个二元组
                    tmp_c[tmp_top]=cc/x[i];
                    sumc=cc%x[i];
                    sumv=sumc*vv;
                }
                top=0;
                for(int j=tmp_top;j>=1;j--){
                    st_v[++top]=tmp_v[j];//倒着赋值
                    st_c[top]=tmp_c[j];
                }
            }
            while(top&&st_v[top]<v[i]){
                ans-=st_v[top]*st_c[top];//减去原本的，再在下面加更大的回来
                c[i]+=st_c[top];//比vi小，变成vi
                top--;
            }
            ans+=one*v[i]*c[i];
            st_v[++top]=v[i];
            st_c[top]=c[i];//自己这个二元组需要放进去
        }
        printf("%lld\n",(ll)(ans%mod));
    }
    return 0;
}