P14258 好感（favor）题解

Wangyixi007 · 2025-10-19 16:18:19 · 题解

首先注意到如果翻了一块下标为 i 的浮板，所需花费为 i。

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

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

所以我们确定了策略：

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

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

至于如何处理，我们可以把每一个要翻转的板的下标记录下来，若第一块板目前已经为第一块了，则翻转第一块，花费为 1，否则反转最后一块，可以用类似维护双向队列来处理。

时间复杂度 O(N)。

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

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