HDU-6383

題目：

度度熊很喜歡數組！！

我們稱一個整數數組為穩定的，若且唯若其同時符合以下兩個條件：

1. 數組里面的元素都是非負整數。
2. 數組里面最大的元素跟最小的元素的差值不超過?1。

舉例而言，[1,2,1,2]?是穩定的，而?[?1,0,?1]?跟?[1,2,3]?都不是。

現在，定義一個在整數數組進行的操作：

* 選擇數組中兩個不同的元素?a?以及?b，將?a?減去?2，以及將?b?加上?1。

舉例而言，[1,2,3]?經過一次操作后，有可能變為?[?1,2,4]?或?[2,2,1]。

現在給定一個整數數組，在任意進行操作后，請問在所有可能達到的穩定數組中，擁有最大的『數組中的最小值』的那些數組，此值是多少呢？

?

?

Input

輸入的第一行有一個正整數?T，代表接下來有幾組測試數據。

對于每組測試數據：
第一行有一個正整數?N。
接下來的一行有?N?個非負整數?xi，代表給定的數組。

*?1≤N≤3×105
*?0≤xi≤108
*?1≤T≤18
* 至多?1?組測試數據中的?N>30000

?

?

Output

對于每一組測試數據，請依序各自在一行內輸出一個整數，代表可能到達的平衡狀態中最大的『數組中的最小值』，如果無法達成平衡狀態，則輸出??1。

?

?

Sample Input

?

2 3 1 2 4 2 0 100000000

?

?

Sample Output

?

2 33333333

?

?

記A為原數列，A*為由A變化成的穩定數列，那么題目所求的就是 所有A*中的最小值 中最大的一個，把這個值記為ans。

首先可以先考慮能不能直接暴力枚舉所有A*，然后求解......?很明顯是不符合實際的。

換種想法，能不能讓ans從無窮大遍歷到0，暴力枚舉所有ans，然后判斷這個ans是否可以構成A*。

那么要先解決判斷的問題。

題目要求的是：* 選擇數組中兩個不同的元素?a?以及?b，將?a?減去?2，以及將?b?加上?1。（這里“不同”指的是下標不同）

也就是進行一次減法（-2），必須要進行一次加法（+1），兩種操作的次數要相等。那么可以分開操作，然后再來看兩種操作的次數。

我們先對原數列A中所有小于ans的數A[i]，做加法，num_p += ans - A[i]

然后對原數列A中所有大于ans+1的數A[i]，做減法，num_m += (A[i] - ans) / 2

這里可能會出現A[i] - ans 是奇數的情況，如：(A[i] - ans) / 2 = 3 /?2 = 1，那么其實這時候，A[i]做完減法后得到的數應該是ans+1，它可以作為這個數列A*的最大值，使得數列A*仍然滿足 “穩定” 的條件。（min：ans，max：ans+1）

接下來要對num_p（進行加法的次數）和 num_m（進行減法的次數）做比較：

num_p =?num_m 的情況：說明這個ans可以作為穩定數列A*的最小值。
num_p !=?num_m 的情況：

首先要了解的一點是：

對于一個數列A，如果它的最小值為min（A），那么它可以通過題目所述的兩種操作，來得到一個穩定數組A*，其最小值仍為min（A）。具體做法是：我們更新數組A，將A中最小值+1，最大值-2，不斷重復這個過程。由于減掉的比加上的多，最終數組A中的最大最小值會不斷地相互逼近，直到最小值為min（A）。

那么對于num_p < num_m：此時當加法減法配對后，仍有一些數需要進行減法操作，也就是說，此時的數列A最小值已經是ans了，存在一些數大于ans+1，那么根據上面的結論，這個數列A是可以得到穩定數組的，所以這個ans合法。

對于num_p > num_m ：此時當加法減法配對后，仍有一些數需要進行加法操作，由于我們進行的是-2，+1，也就是總的來說肯定是朝減少的方向進行，既然出現還要加上的操作，只能說明這個ans還太大了，滿足不了，得不到穩定數組。

?

解決完判斷的問題，剩下的就是對ans的范圍從原先的 0～∞ 進一步縮減。

很明顯的上界應當為數列A的最大值max（A）：倘若大于max（A）的話，那么A中所有的數都要往上加才行，由于有減法操作，實現不了；

下界應當為數列A的最小值min（A）：在前面紅色的結論已經說明了，ans至少會等于min（A）。

那么可以看出采用的算法應該是二分法，邊界：min（A）～ max（A）

代碼：

// // main.cpp // 初賽B1004 // // Created by jinyu on 2018/8/13. // Copyright ? 2018年 jinyu. All rights reserved. //#include <iostream> #include <cstdio> #include <algorithm> using namespace std;typedef long long LL; const int MAXN = 3e5+7; const long long INF = 0x3f3f3f3f3f3f;long long A[MAXN]; int N;bool judge(LL ans){LL num_p = 0;LL num_m = 0;for(int i = 0;i<N;++i){if(ans > A[i])num_p += ans-A[i];else if(ans+1 < A[i])num_m += (A[i]-ans)/2;}return num_m>=num_p; }int main(){int T;scanf("%d",&T);while (T--) {scanf("%d",&N);LL R = -1;LL L = INF;for(int i = 0;i<N;++i)scanf("%lld",&A[i]);sort(A,A+N);L = A[0];R = A[N-1];LL ans = -1;while(L<=R){LL mid = (L+R)/2;if(judge(mid)){L = mid + 1;ans = mid;}elseR = mid - 1;}printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的2018百度之星程序设计大赛初赛B——1004p1m2的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。