修改数组（洛谷P7285题题解，C++语言描述）

题目要求

P7285题目链接

分析

这题虽然是红题，但是因为很有趣且是 Special Judge ，所以写篇题解。

乍一看，这题好麻烦啊，要综合考虑 x x x和 y y y，达到 x − y x-y x−y的最优化。 实际上，洛谷的 Special Judge 一般都有一些“奇怪”的思路。

第一行输入就是告诉你一共有几组问题，而每组内第一行是一共几个0/1的数字，第二行是串。

我在纸上画了画图，开始想的是，会不会是间距最小的连起来是最优的，然后再考虑考虑连起来别的。

画着画着，发现怎么算都是把最所有的1连起来（即最接近两端的1连起来），那这道题就可以用贪心思想去解决。

用通俗的语言简单地做一下理论分析： 要让 x − y x-y x−y最大， x x x表示最长连续1串长度，而 y y y表示修改的元素个数。 修改的肯定是0改1（否则就是只加 y y y不加 x x x， x − y x-y x−y不会增大），不然肯定不能增大 x − y x-y x−y。 那我们每一次从最长1串的一端将0改成1，其实 x x x会加1，而 y y y也会加1， x − y x-y x−y不变（如果从中间改，那就只加 y y y不加 x x x， x − y x-y x−y会减少）。 虽然说逐个把接近1的0改成1只能使得 x − y x-y x−y不变，但是每当将两个含1的串连起来的时候，就相当于我们玩游戏的时候通过某个关卡附带一个奖励品一样，我们没有去改0，也就是 y y y没变，但 x x x增大，所以 x − y x-y x−y增大了。 也就是说，我们只需要从最长1串的一端出发，将尽可能多的0改成1，这个过程 x − y x-y x−y不变，而每次遇到另一个1串的一端， x − y x-y x−y会增大，多多益善，贪心思想！

在考虑到此题的处理难度，既然从最长1串出发的0改1不会使得 x − y x-y x−y变小，那就干脆把所有的0改成1就好了！

再看看 x − y x-y x−y此时到底是什么吧： x x x是整个0/1串的长度， y y y是串里含0的个数，所以 x − y x-y x−y表示的就是串里含1的个数。

所以每读进来一个串，识别一下有多少个1就是 x − y x-y x−y，而再按 x x x的个数输出一下1即可AC。

AC代码

#include 

using namespace std;

int main() {
    int n, m, temp, one_count;
    cin >> n;
    for (int i = 0; i > m;
        one_count = 0;
        for (int j = 0; j > temp;
            if (temp == 1) {
                one_count++;
            }
        }
        cout