AC代碼

https://codeforces.com/contest/1775/submission/189892616

題意：

給定一個數(shù)字序列a1，a2，…，你可以對這個序列執(zhí)行幾個操作。

每個操作應(yīng)如下所示。您可以選擇一些子序列。

(相關(guān)資料圖)

然后你把這個子序列中奇數(shù)位置的所有數(shù)字稱為北方，把這個子順序中偶數(shù)位置的所有數(shù)值稱為南方。

在這種情況下，只考慮數(shù)字在子序列中的位置，而不是在原始序列中。

例如，考慮序列1,4,2,8,5,7,3,6,9及其子序列4,2,5,6。

然后數(shù)字4和5是北方，數(shù)字2和6是南方。

之后，您可以執(zhí)行以下操作之一：

所有北方數(shù)字加1，所有南方數(shù)字減1；或

所有南方數(shù)字加1，所有北方數(shù)字減1。

因此，從序列4,2,5,6中， 則可以得到 5、1、6、 5或3、3、4、7。

然后操作結(jié)束。還要注意，所有的操作都是獨立的，即當(dāng)一個操作結(jié)束時，數(shù)字不再被稱為北方或南方。

現(xiàn)在要使用上述操作將序列的所有數(shù)字轉(zhuǎn)換為零。求最少操作次數(shù)是多少。

題解：

前綴和

標(biāo)簽： HTTPS