#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,m; cin >> n >> m; vector<int> greed(n); for (int i = 0; i<n; i++)cin >> greed[i]; vector<int> req={m}; if (n==1){ cout << m << '\n'; return 0; } for (int i = n-2; i>=0; i--){ int votes=(n-i+1)/2-1; int free=0; priority_queue<pair<int,int>> pq; for (int j = 0; j<(int)req.size(); j++){ if (req[j]==-1){ free++; continue; } pq.push({req[j]+greed[n-1-j],j}); } while((int)pq.size()+free>votes)pq.pop(); vector<int> now(n-i); int sm=0; while(pq.size()){ now[pq.top().second]=pq.top().first; sm+=pq.top().first; pq.pop(); } if (sm<=m){ now.back()=m-sm; swap(now,req); } else req.push_back(-1); } reverse(req.begin(),req.end()); for (int i = 0; i<n; i++)cout << req[i] << ' '; cout << '\n'; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,m; cin >> n >> m; vector<int> greed(n); for (int i = 0; i<n; i++)cin >> greed[i]; vector<int> req={m}; if (n==1){ cout << m << '\n'; return 0; } for (int i = n-2; i>=0; i--){ int votes=(n-i+1)/2-1; int free=0; priority_queue<pair<int,int>> pq; for (int j = 0; j<(int)req.size(); j++){ if (req[j]==-1){ free++; continue; } pq.push({req[j]+greed[n-1-j],j}); } while((int)pq.size()+free>votes)pq.pop(); vector<int> now(n-i); int sm=0; while(pq.size()){ now[pq.top().second]=pq.top().first; sm+=pq.top().first; pq.pop(); } if (sm<=m){ now.back()=m-sm; swap(now,req); } else req.push_back(-1); } reverse(req.begin(),req.end()); for (int i = 0; i<n; i++)cout << req[i] << ' '; cout << '\n'; } |