Acwing 3686 [贪心]移动序列

题目

https://www.acwing.com/problem/content/3689/

思路

我尝试统计第一个1开始到最后一个1结束的区间内0的个数(直觉)但是并不会实现

Y总的讲解就非常的浅显易懂:
F(x):所有相邻两个1之间0的个数,则本题的目标是使得F()恒等于零

那么对上图抽象化的三段区间,其移动的结果为:

左区间左移:F()+1
左区间右移:F()-1
中区间左移:F()
中区间右移:F()
右区间左移:F()-1
右区间右移:F()+1

则每次进行操作至多使得F()-1,此时可用贪心法解决。整个算法统计所有的相邻两个1之间的0的个数即可
PS:每次让最左区间向右走即可,因为区间会合并

实现 C++

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;

        int res = 0, last = -1;
        for (int i = 0; i < n; i++)
        {
            int x;
            cin >> x;
            if (x)
            {
                if (last != -1)
                    res += i - last - 1;
                last = i;
            }
        }
        cout << res << endl;
    }

    return 0;
}

发表评论