题解：P14258 好感（favor）

· · 题解

这里提供一个简单易懂的贪心+模拟方法。

思路

使用模拟的思路很简单。

因为把所有浮板翻成正面朝上和反面朝上使用的思路相同，所以这里以把所有浮板都翻成 ch 为例，其中 ch 为目标字符（0 或 1）。

那么我们要怎样才能保证移动的距离总和最小呢？

首先注意到如果翻了最后一个 ch，那么前面的所有 ch 都会向前移动一个单位，这样总的最终距离会缩短很多，当然是最贪心的思路。

但是是不是所有时候都可以将最后一个 ch 进行翻面呢？当然不是。如果当前最前面的字符是 ch，那么翻动最后面的 ch 时，最前面的 ch 就会非常难受的移到最后一个 ch 的后面，这样当然就不能保证最优了!

所以，最终的贪心方法是：

由于每翻动一次浮板，影响到的是前面和自身的所有浮板，所以考虑使用两个指针 l,r 分别指向最前面和最后面的目标字符进行模拟，类似于双指针。

初始化

输入字符串 s 时先在前面加上一个空格，使下标从 1 开始，方便后面的处理。

指针 l 开始是 1，因为要从开头开始模拟。指针 r 需要找到最后一个 ch，那么我们可以直接遍历找最后一个 ch，如果没找到就返回极大值表示不能将所有浮板都翻成 ch 朝上的状态。

开始模拟

我们使用一个 while 循环，当两个指针 l,r 没有在同一点上时持续模拟。

首先考虑指针 l 所处位置的字符是否是 ch。如果是，那么要先翻动它，移动距离为 1，并且我们要标记这个字符已经计算过了，标记为任意一个不为 0,1 的字符。

再考虑指针 r 所处位置的字符是否是 ch。如果是，那么就翻动它，移动的距离为 r-l+1。这里有个细节，就是翻动最后一个 ch 造成前面移动一个单位的这个移动不需要模拟出来，因为这个移动会把最前面的字符移到最后面的 ch 的后面，也就等同于把最前面的指针 l 加了 1。这样处理就可以避免模拟大量的移动，从而减少时间复杂度了。

循环的每一次，r 都要减 1 来往前面找。

最后返回累加的移动时间就是将所有浮板翻动成 ch 朝上所需要的时间。答案的话就是翻成正面和反面所需时间的最小值了。时间复杂度为\mathcal{O}(T\times n)。

代码解决

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,n;
string s;
int count(string s,char ch){
    int l=1,r=-1,ans=0;
    for(int i=1;i<=n;i++)if(s[i]==ch)r=i;
    if(r==-1)return 1e9;
    while(l<=r){
        if(s[l]==ch){
            ans++;
            s[l]='#';
        }
        if(s[r]==ch){
            ans+=(r-l+1);
            l++;
        }
        r--;
    }
    return ans;
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
    while(T--){
        cin>>n>>s;
        s=" "+s;
        cout<<min(count(s,'1'),count(s,'0'))<<"\n"; 
    }
    return 0;
}