Hướng dẫn giải của Thi thử HSG9 2026 - Ngày 4 - Đã xem
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Vì tính chất các số bị thiếu không giảm và chỉ cách nhau một đơn vị, rõ ràng các số bị thiếu phải có dạng ~x,\ x,\ x,\ ...,\ x, x + 1,\ x + 1,\ ...~. Do đó nếu như gọi ~C~ là số lượng và ~S~ là tổng của các số bị thiếu (tính bằng cách lấy ~n\times k~ trừ đi tổng các số đã có) thì ta sẽ tìm được các số bị thiếu có dạng:
- ~S\ \%\ C~ số bị thiếu cuối cùng sẽ là ~\lfloor\frac{S}{C}\rfloor + 1~ với ~\%~ là phép chia lấy dư.
- Những số bị thiếu còn lại sẽ là ~\lfloor\frac{S}{C}\rfloor~.
Code mẫu (người dùng nongducquan):
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std;
typedef pair<ll, ll> ii;
typedef unsigned long long INT;
const ll maxn = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll N = 5e5;
const ll base = 1e5 + 3;
const ll inf = 1e18;
ll n, k, a[maxn], s, cnt;
vector<ll> pos;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen("SEEN.inp", "r", stdin);
freopen("SEEN.out", "w", stdout);
cin>>n>>k;
s = n * k;
for (int i = 1; i <= n; i++) {
cin>>a[i];
if (a[i] >= 0) s -= a[i];
else {
cnt++;
pos.push_back(i);
}
}
ll value = s / cnt, du = s % cnt;
for (int i = 0; i < pos.size(); i++) {
if (i < cnt - du) a[pos[i]] = value;
else a[pos[i]] = value + 1;
}
for (int i = 1; i <= n; i++) cout<<a[i]<<' ';
}
Bình luận