题解：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：

CPP

#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;
}

题解：P9499 「RiOI-2」change

文章操作

0.前言：

1.思路：

2.细节：

3.AC code：

相关推荐

评论

题解：P9499 「RiOI-2」change