题解：P14258 好感（favor）

tag：贪心。

暴力

浮板只有

2^n

种状态，记忆化搜索即可。期望得分

20

。

贪心策略

首先确定最终要变成正面或者反面，不妨设为正面，实现时求出两种情况答案再取

\min

即可。接下来我们将浮板分为需要翻面的（即反面）和不需要翻面的（即正面）。

将浮板

k

翻面时，总移动距离会增加

k

，同时所有

i<k

的反面浮板

i

会移动到

i-1

，这会使得它之后每次被翻面时需要的移动距离减少

1

。

如果有正面朝上的浮板被翻过面，不妨设其中被翻面时下标最小的一个当时为浮板

k

。则

k

前面没有浮板正面朝上时被翻面，因此每个浮板至多在反面朝上时被翻过一次面。从而若这一步不给

k

翻面，减少的移动距离为

k

，前面的至多

k-1

个浮板每个翻面时的移动距离至多增加

1

，因此总移动距离减少。

重复以上调整，可以得知只将反面浮板翻面，对于不需要翻面的浮板则从不翻面，能够达到最优答案。此时每个浮板至多翻面一次，同上分析得每次翻面对最终总移动距离的增加至少为

1

。

如果某一次将

k\ge2

翻面时浮板

1

为反面，则它会被移动到

k

，而在将

k

翻面前先将

1

翻面只需要移动

1

。因此每当一个反面浮板到达

1

，则优先将它翻面。

显然此时我们可以贪心地每次选取最大的

k

，这样最初的每个反面浮板

i

最终实际需要的移动距离为

\max\{1,i-\sum_{k>i}[k 为反面]\}

。容易证明这是最优答案。

直接模拟上述翻面过程可以做到

O(n^2)

，期望得分

60

。

Code:

CPP

int m;
int p[1000003];
inline ll calc(){
	ll res=0;
	for(int i=m;i>0&&p[i]>=1;--i){
		res+=p[i];
		for(int j=i-1;j>0&&p[j]>=1;--j){
			if(p[j]==1)++res;
			--p[j];
		}
	}return res;
}

int n;
ll rs0,rs1;
char s[1000003];
inline void solve(){
	cin>>n>>s+1;m=0;
	for(int i=1;i<=n;++i)
		if(s[i]=='0')p[++m]=i;
	rs0=calc();m=0;
	for(int i=1;i<=n;++i)
		if(s[i]=='1')p[++m]=i;
	rs1=calc();cout<<min(rs0,rs1)<<"\n";
}

特殊性质

其实是为了多给点部分分。可以直接计算将前

m

个正面变为反面需要的移动距离为

\begin{cases} k^2+k-1,&m=2k-1\\ k^2+2k,&m=2k \end{cases}

，将后

n-m

个反面变为正面需要的移动距离为

(n-m)(m+1)

。注意后一个式子没有考虑

n-m

过大的情况，但事实上这时前一部分的答案总是较小，因此直接对以上两结果取

\min

即可。期望得分

40

，结合朴素贪心期望得分

80

。

正解

事实上由上面得出的移动距离公式可以

O(1)

计算出每个浮板

i

的贡献。

具体实现中可以记录一个变量

c

表示现在已经翻了几个浮板。枚举要翻面的浮板最大下标

p_j

，同时记录剩余的最小下标

p_i

，将最大浮板翻面移动距离为

p_j-c

，若它是第

c

个被翻面的浮板并且

p_i=c

，则这次翻面时

p_i

到达了

1

的位置，如果

i

不等于刚刚翻面的

j

则直接给答案加上

1

，并处理掉

p_i

。

总时间复杂度

O(n)

，期望得分

100

。记得开 long long。

Code:

CPP

int m;
int p[1000003];
inline ll calc(){
	ll res=0;
	for(int i=1,j=m,c=0;j>=i;){
		res+=p[j]-c;++c;--j;
		if(i<=j&&p[i]==c)++res,++i;
	}return res;
}

题解：P14258 好感（favor）

文章操作

暴力

贪心策略

特殊性质

正解

相关推荐

评论

题解：P14258 好感（favor）