ARC 118 B - Village of M People 解説

atcoder.jp

問題

Nが のようにK分割されている。Mが与えられるので同様にK分割し、その結果を整数列Bとしたとき、 が最小となるようなものを1つ出力せよ。

制約

解説

数列Bの要素として実数を許すなら、 とすることで、 を全て0にすることができる。

しかし、Bは整数列である必要があるので、上記の差が最小になるように各要素を切り下げ、または切り上げ、合計がMになるようにする必要がある。

一旦、全てのB_iは切り捨てることにすると となる。これらの総和を sum とすると、M-sum 個が切り上げる必要がある要素数になる。

切り上げるべき要素は、 の小数部分がより大きいものを切り上げた方が得なので、各要素を の値でソートし、大きいものから M-sum 個を切り上げる。

実装

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = (int)(0); i < (int)(n); ++i)
using ll = long long;
template<class t> using vc=vector<t>;

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  int k,n,m; cin>>k>>n>>m;
  vc<ll> a(k);
  rep(i,k) cin>>a[i];
  
  vc<pair<int,int>> p(k);
  rep(i,k){
    p[i]={a[i]*m%n,i};
  }
  sort(p.rbegin(),p.rend());
  
  vc<int> b(k);
  
  int sum=0;
  rep(i,k){
    int z,h; tie(z,h)=p[i];
    
    int x=a[h]*m/n;
    b[h]=x;
    sum+=b[h];
  }
  int rem=m-sum;
  rep(i,rem){
    int z,h; tie(z,h)=p[i];
    b[h]++;
  }
  
  rep(i,k) cout<<b[i]<<endl;
}