題目要求

P7285題目鏈接

分析

這題雖然是紅題，但是因為很有趣且是 Special Judge ，所以寫篇題解。

乍一看，這題好麻煩啊，要綜合考慮$x$和$y$，達到$x?y$的最優(yōu)化。
實際上，洛谷的 Special Judge 一般都有一些“奇怪”的思路。

第一行輸入就是告訴你一共有幾組問題，而每組內(nèi)第一行是一共幾個0/1的數(shù)字，第二行是串。

我在紙上畫了畫圖，開始想的是，會不會是間距最小的連起來是最優(yōu)的，然后再考慮考慮連起來別的。

畫著畫著，發(fā)現(xiàn)怎么算都是把最所有的1連起來（即最接近兩端的1連起來），那這道題就可以用貪心思想去解決。

用通俗的語言簡單地做一下理論分析：
要讓$x?y$最大，$x$表示最長連續(xù)1串長度，而$y$表示修改的元素個數(shù)。
修改的肯定是0改1（否則就是只加$y$不加$x$，$x?y$不會增大），不然肯定不能增大$x?y$。
那我們每一次從最長1串的一端將0改成1，其實$x$會加1，而$y$也會加1，$x?y$不變（如果從中間改，那就只加$y$不加$x$，$x?y$會減少）。
雖然說逐個把接近1的0改成1只能使得$x?y$不變，但是每當(dāng)將兩個含1的串連起來的時候，就相當(dāng)于我們玩游戲的時候通過某個關(guān)卡附帶一個獎勵品一樣，我們沒有去改0，也就是$y$沒變，但$x$增大，所以$x?y$增大了。
也就是說，我們只需要從最長1串的一端出發(fā)，將盡可能多的0改成1，這個過程$x?y$不變，而每次遇到另一個1串的一端，$x?y$會增大，多多益善，貪心思想！

在考慮到此題的處理難度，既然從最長1串出發(fā)的0改1不會使得$x?y$變小，那就干脆把所有的0改成1就好了！

再看看$x?y$此時到底是什么吧：$x$是整個0/1串的長度，$y$是串里含0的個數(shù)，所以$x?y$表示的就是串里含1的個數(shù)。

所以每讀進來一個串，識別一下有多少個1就是$x?y$，而再按$x$的個數(shù)輸出一下1即可AC。

AC代碼

#include <iostream>using namespace std;int main() {int n, m, temp, one_count;cin >> n;for (int i = 0; i < n; i++) {cin >> m;one_count = 0;for (int j = 0; j < m; j++) {cin >> temp;if (temp == 1) {one_count++;}}cout << one_count << endl;for (int j = 0; j < m; j++) {cout << 1 << ' ';}cout<<endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的修改数组（洛谷P7285题题解，C++语言描述）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。