当前位置：首页 > news >正文

P10311 Weighted Mean Sol

news 2026/6/10 17:57:46

题目链接

一道有些复杂的构造。

不妨设加权平均数为 \(\lambda\)。通过代换，就有了 \(\sum\limits_{i=1}^n b_i \cdot (a_i - \lambda) = 0\)。因此现在变成尝试构造 \(\lambda\)。

显然的，排序对于答案的构造没有影响，因此下文中，数组默认有序。同时，记 \(c_i = a_i - \lambda\)。

n为奇数

最为简单的情况。考虑直接取中位数为 \(\lambda\)，则显然的，我们可以对称的让两项为 \(0\)，这里不再赘述。

而对于中间位置，直接取到 \(m\)，正确性显然。

n为偶数

这里又有分讨。定义 \(L = a[n/2],R = a[n/2+1]\)。

L \(\ne\) R-1

那么考虑取 \(\lambda\) 为 \(L+1\)，显然上述构造成立。

L = R-1

本题最复杂的情况。

我们如果考虑取 \(\lambda = L\)，然后删除 \(R\)，并让 \(c_n + 1\)。那么这样又能构造了。但是会出现三个位置相同的情况。

我们需要证明，只要 \(n\) 不为 2，答案一定存在。考虑什么情况下不合法，显然是 \(c_1,c_n\) 产生了对应，那么只要重新取 \(\lambda = R\)，就一定正确了。

而对于 \(n=2\) 不合法，证明是显然的。

Code

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define File(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define LL long long
#define fi first
#define se second
const int N = 1e6 + 10;
struct node{int val,id;
};
bool cmp(node x,node y){return x.val < y.val;
}
node a[N];
int b[N];
int tmp[N];
int n,m;
unordered_map<int,int> mp;
int ans[N];
void print(){for(int i=1;i<=n;i++)cout << ans[i] << " ";cout << "\n";
}
void solve(){cin >> n >> m;for(int i=1;i<=n;i++){cin >> a[i].val;a[i].id = i;}sort(a+1,a+1+n,cmp);if(n & 1){int k = ((n+1) / 2);b[k] = m;int c = a[k].val;for(int i=1;i<=n;i++)a[i].val -= c;for(int i=1;i<=n;i++)b[i] = a[i].val;b[k] = m;reverse(b+1,b+1+n);for(int i=1;i<=n;i++)ans[a[i].id] = abs(b[i]);print();return ;}else{int L,R;L = n/2,R = L + 1;if(n ==2  && a[L].val == a[R].val-1){cout << -1 << "\n";return ;}if(a[L].val == a[R].val-1){vector<int> c(n,0);vector<bool> vis(n+1,0);int tot = 0;int num = a[L].val;for(int i=1;i<=L;i++){c[++tot] = a[i].val - num;c[tot] = abs(c[tot]);}for(int i=R+1;i<=n;i++)c[++tot] = a[i].val - num;c[tot] ++ ;set<int> st;st.clear();for(int i=1;i<L;i++)st.insert(c[i]);for(int i=L+1;i<=tot;i++)st.erase(c[i]);if(!st.empty()){for(int i=1;i<=n;i++){if(c[i] == (*st.begin())){b[i] = c[tot];b[n/2+1] = b[n] = c[i];vis[i] = vis[n/2+1] = vis[n] = 1;st.clear();break;}}b[n/2] = m;int nw = L+2;for(int i=1;i<n/2;i++){if(vis[nw]) nw ++ ;if(vis[i]) continue;b[nw] = c[i];b[i] = c[nw-1];nw ++ ;}for(int i=1;i<=n;i++)ans[a[i].id] = b[i];print();return ;}reverse(a+1,a+1+n);for(int i=1;i<=n-1;i++)c[i] = 0;for(int i=1;i<=n;i++)vis[i] = 0;tot = 0;num = a[L].val;for(int i=1;i<=L;i++){c[++tot] = a[i].val - num;c[tot] = abs(c[tot]);}for(int i=R+1;i<=n;i++){c[++tot] = a[i].val - num;c[tot] = abs(c[tot]);}c[tot] ++ ;st.clear();for(int i=1;i<L;i++)st.insert(c[i]);for(int i=L+1;i<=tot;i++)st.erase(c[i]);if(!st.empty()){for(int i=1;i<=n;i++){if(c[i] == (*st.begin())){b[i] = c[tot];b[n/2+1] = b[n] = c[i];vis[i] = vis[n/2+1] = vis[n] = 1;st.clear();break;}}b[n/2] = m;int nw = L+2;for(int i=1;i<n/2;i++){if(vis[nw]) nw ++ ;if(vis[i]) continue;b[nw] = c[i];b[i] = c[nw-1];nw ++ ;}for(int i=1;i<=n;i++)ans[a[i].id] = b[i];print();return ;}}else{int c = a[L].val + 1;for(int i=1;i<=n;i++)a[i].val -= c;for(int i=1;i<=n;i++)b[i] = a[i].val;reverse(b+1,b+1+n);for(int i=1;i<=n;i++)ans[a[i].id] = abs(b[i]);print();}}
}
int main(){IOS;int T;cin >> T;while(T -- )solve();return 0;
}