p1m2

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 736????Accepted Submission(s): 268

Problem Description

度度熊很喜歡數組！！

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

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

Source

2018 “百度之星”程序設計大賽 - 初賽（B）

解析：可以證明，最后的-2，+1的數組肯定可以變成穩定數組。因為我們每次的操作相當于把兩個數的和減一，兩次就是每個數-1.（a-2，b+1,? ? a+1,b-2）。最后肯定可以變成01這樣的數組，就是穩定數組。在變化的過程有穩定數組的存在。說明我們就可以求的答案。

二分枚舉。判斷左邊的操作次數與右邊的操作次數，若是右邊的大于等于左邊的，說明答案可能存在mid往上的某一個數，反之亦然。

#include<bits/stdc++.h> using namespace std;#define e exp(1) #define pi acos(-1) #define mod 1000000007 #define inf 0x3f3f3f3f #define ll long long #define ull unsigned long long #define mem(a,b) memset(a,b,sizeof(a)) int gcd(int a,int b){return b?gcd(b,a%b):a;}int a[300005]; int main() {int T;scanf("%d",&T);while(T--){int n;scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&a[i]);}sort(a,a+n);int l=0,r=1e8;int ans=0;while(l<=r){ll x=0,y=0;int mid=l+r>>1;for(int i=0; i<n; i++){if(mid>a[i])x+=mid-a[i];if(mid<a[i])y+=(a[i]-mid)/2;}if(x<=y){ans=max(ans,mid);l=mid+1;}else r=mid-1;}printf("%d\n",ans);}return 0; }

?

總結

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

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