在所有可能的B[i]序列，求一个B序列这个公式的最大值最小。二分最值。
[|frac{B[i]}{M} - frac{A[i]}{N}|
\
-frac{mid}{N * M} <= frac{B[i] * N - A[i] * M }{N * m}<= frac{mid}{N * M}
\l = frac{-mid + A[i] * M + N - 1}{N} , r = frac{mid + A[i] * M}{N}
]
满足条件即可判断成立
[sum_{i=1}^{k}l[i] <= m &&m <= sum_{i = 1}^{k}r[i]
]
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimize(3 , "Ofast" , "inline")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <map>
#include <list>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <stack>
#include <set>
#include <bitset>
#include <deque>
using namespace std ;
#define ios ios::sync_with_stdio(false) , cin.tie(0)
#define x first
#define y second
#define pb push_back
#define ls rt << 1
#define rs rt << 1 | 1
typedef long long ll ;
const double esp = 1e-6 , pi = acos(-1) ;
typedef pair<int , int> PII ;
const int N = 1e6 + 10 , INF = 0x3f3f3f3f , mod = 1e9 + 7;
int n , m , k ;
int a[N] ;
PII b[N] ;
bool check(int mid) {
ll L = 0 , R = 0 ;
vector<pair<int , int>> v(k + 1) ;
for(int i = 1; i <= k ;i ++ ) {
ll l = max(0ll , ((1ll * m * a[i] - 1ll * mid + n - 1ll)/ n)) ;
ll r = ((1ll * m * a[i] + 1ll * mid )/ n) ;
L += l ;
R += r ;
v[i] = {l , r} ;
}
if(L <= m && m <= R){
for(int i = 1; i <= k ; i ++ )
b[i] = v[i] ;
return true ;
}
return false ;
}
int ans[N] ;
int work()
{
cin >> k >> n >> m ;
for(int i = 1 ;i <= k ;i ++ ) cin >> a[i] ;
int l = 1 , r = INF ;
while(l <= r) {
int mid = l + r >> 1 ;
if(check(mid)) r = mid - 1 ;
else l = mid + 1 ;
}
for(int i = 1; i <= k ;i ++ )
ans[i] = b[i].x , m -= b[i].x ;
for(int i = 1; i <= k ;i ++ ) {
int t = min(m , b[i].y - b[i].x) ;
m -= t ;
ans[i] += t ;
cout << ans[i] << " " ;
}
puts("") ;
// cout << ans << "
" ;
return 0 ;
}
int main()
{
// freopen("C://Users//spnooyseed//Desktop//in.txt" , "r" , stdin) ;
// freopen("C://Users//spnooyseed//Desktop//out.txt" , "w" , stdout) ;
work() ;
return 0 ;
}
/*
*/