KEYENCE Programming Contest 2019 C - Exam and Wizard(400)

概要

与えられた数列に対して、数列を下記のように構成したい。

• すべてのに対し、
• との総和が等しい

はなるの数が最小になるように構成したい。この最小値を出力せよ。
また、が構成できないときは-1を出力せよ。

制約

方針

の総和がの総和より小さいとき、は構成できない。

それ以外の場合、は構成可能である。
構成方法のしては、なるが存在した場合、でかつが最も大きいものから、との差を補填してゆくイメージ。

解答

Submission #4011619 - KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, int> pli;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int n;
	cin >> n;
 
	ll a[n];
	ll asum = 0;
 
	rep(i, n) {
		cin >> a[i];
		asum += a[i];
	}
 
	ll b[n];
	vector<ll> v;
	ll bsum = 0;
	rep(i, n) {
		cin >> b[i];
		if(a[i] > b[i]) v.push_back(a[i] - b[i]);
		bsum += b[i];
	}
 
	if(asum < bsum){
		cout << -1 << endl;
		return 0;
	}
 
	sort(v.begin(), v.end(), greater<ll>());
	v.insert(v.begin(), 0);
 
	ll ans = 0;
	rep(i, n){
		ll d = b[i] - a[i];
		if(d <= 0) continue;
 
		ans++;
		while(d > 0){
			if(v[0] > d){
				v[0] -= d;
				d = 0;
			}else{
				d -= v[0];
				v.erase(v.begin());
				ans++;
			}
		}
	}
 
	cout << ans << endl;
}