P14258 好感（favor）题解

首先注意到如果翻了一块下标为

i

的浮板，所需花费为

i

。

又因为如果第一块浮板是要翻转的，那么翻转后面的显然不优，因为如果是第一块板，反转过后会和首先反转的板交换位置，所以肯定劣于翻转第一块板。

再考虑翻转的优先顺序，因为翻转了一块板会使前面的板都向前挪，所以会减少等同于前面所有要翻转的板的数量的花费，因此先翻后面的板更优。

所以我们确定了策略：

如果第一块板是要翻转的则翻转，否则不翻转。

因为我们不知道都翻到正面更优还是都翻到反面更优，所以可以选择都进行运算。

至于如何处理，我们可以把每一个要翻转的板的下标记录下来，若第一块板目前已经为第一块了，则翻转第一块，花费为

1

，否则反转最后一块，可以用类似维护双向队列来处理。

时间复杂度

O(N)

。

（另外此题还有许多细节，赛时调了挺久的）

CPP

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e6+5;

int a0[N],a1[N];

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
//	freopen("favor3.in","r",stdin);
	string b;
	int t,len,ans0,ans1,l0,l1,r0,r1,cnt0,cnt1;//cnt0,cnt1表示前面的板都已经向前挪过了几次，因为若要动态修改，复杂度为O(N)，显然不能接受，又因为从后往前翻转，所以不用考虑是否该位置能前移
	cin>>t;
	while(t--){
		cin>>len>>b;
		l0=1,l1=1,ans0=0,ans1=0,r0=0,r1=0,cnt0=0,cnt1=0;
		for(int i=0;i<len;i++){
			if(b[i]=='0'){
				r0++;
				a0[r0]=i+1;
			}
			else{
				r1++;
				a1[r1]=i+1;
			}
		}
		while(l0<=r0){
			if(a0[l0]-cnt0==1){
				l0++;
				ans0++;
			}
			else{
				ans0+=a0[r0]-cnt0;
				cnt0++;
				r0--;
			}
		}
		while(l1<=r1){
			if(a1[l1]-cnt1==1){
				l1++;
				ans1++;
			}
			else{
				ans1+=a1[r1]-cnt1;
			cnt1++;
			r1--;
			}
		}
		cout<<min(ans0,ans1)<<'\n';
	}
    return 0;
}

P14258 好感（favor）题解

文章操作

相关推荐

评论

P14258 好感（favor）题解