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

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:

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