正題

題目鏈接:https://ac.nowcoder.com/acm/contest/7413/C

---

題目大意

給一個序列$A$，求兩個$a,b$使得$$\sum _{i=1}^n\sum _{j=1}^{n}max\{|A_i?a|,|A_j?b|\}$$最小。

---

解題思路

因為是取$max$，也就是$a,b$中最劣的那一個，所以顯然有$a=b$。

考慮如和求$a$，不難發現其實答案就是對于每個$\frac{A_i+A_j}{2}$的中位數。我們可以二分答案，然后求在$mid$前有多少個$A_i+A_j$，這個顯然也可以將數組排序后二分求得（其實不二分用指針也行）。

時間復雜度$O(n{\log }^{2}n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll XJQ=1e9+7; ll n,a[110000]; ll find(ll x){ll l=1,r=n;while(l<=r){ll mid=(l+r)>>1;if(a[mid]<=x)l=mid+1;else r=mid-1;}return r; } ll check(ll mid){ll ans=0;for(ll i=1;i<=n;i++)ans+=find(mid-a[i]);return ans; } int main() {scanf("%lld",&n);for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);sort(a+1,a+1+n);ll l=1,r=1e9,k=n*n;while(l<=r){ll mid=(l+r)>>1;if(check(mid)>=(k+1)/2)r=mid-1;else l=mid+1;}ll ans=0;for(ll i=1;i<=n;i++)a[i]=abs(a[i]*2-l);sort(a+1,a+1+n);for(ll i=1;i<=n;i++)ans+=a[i]*((i-1)*2+1);printf("%lld",ans%XJQ); }

總結

以上是生活随笔為你收集整理的牛客挑战赛43C-最优公式【二分】的全部內容，希望文章能夠幫你解決所遇到的問題。

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