一. 七天假日 T2

? ? ? ? 原思路：直接計算左右括號的數量，然后直接輸出他們的差

? ? ? ? 改進思路： 用d值記錄截止到當前位置，還需要多少個右括號可以滿足非法要求

? ? ? ? cur：截止到當前位置，已經有多少個右括號

? ? ? ? sum是右括號位置的前綴和；

? ? ? ? 假設當前位置為i，需要從i開始有d+1個右括號，那么從0到i+d的字符串就是一個非法的字符串： sum[cur+d+1]-sum[cur]是后面d+1右括號的位置和，我要把這d+1個右括號移動到 i-d+i ,i-d+i的位置和使用等差數列求和（i+i+d）*(d+1)/2? 差值最小值就是答案

? ? ? ? 代碼：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int sum[N],t;
signed main(){cin>>t;while(t--){string s;cin>>s;int n=s.size()/2;for(int i=0,j=0;i<n*2;i++){if(s[i]==')')sum[++j]=i;}for(int i=1;i<=n;i++)sum[i]+=sum[i-1];int d=0,cur=0,ans=9e18;for(int i=0;i<n*2;i++){if(cur+d+1<=n) ans=min(ans,sum[cur+d+1]-sum[cur]-(2*i+d)*(d+1)/2);if(s[i]=='(') d++;else d--,cur++;}cout<<ans<<endl;}return 0;
}
/*
3
()
(())
(()()())(((())))(()())
*/

二.辛酸風味 T3

? ? ? ? 需要保證平均數也是中位數?

? ? ? ? 如果平均數比中位數大 那么我們需要保證中位數到這個二分的值全是mid才能保證

中位數=平均數，差值為res? ?左邊界為max(（所有數的和+n-1）/n,a[中位值]),右邊界為1e9

隨后進行二分操作? 如果n*mid-res-sum? 則mid為答案??

? ? ? ? 代碼：

????????

#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=2e5+10;
int t,n,a[N],s[N],sum;
signed main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0); cin>>t;while(t--){cin>>n;sum=0;for(int i=1;i<=n;i++){cin>>a[i];sum+=a[i];}sort(a+1,a+n+1);for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];int pos=(n+1)/2,res=0;int l=max((sum+n-1)/n,a[pos]),r=1e9;while(l<r){int mid=l+r>>1;int x=lower_bound(a+1,a+n+1,mid)-a;if(x>=pos) res=(x-pos)*mid-(s[x-1]-s[pos-1]);else res=0;if(n*mid-sum-res>=0) r=mid;else l=mid+1;}cout<<n*l-sum<<endl;}return 0;
}