AtCoder蟻本 初級編 2-4 データ構造 ①Expedition

CODE THANKS FESTIVAL 2017 C - Factory (300)

C: Factory - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder

概要

項の数列が与えられる。から数を回選んでその合計を求めることを考える。ただし、各は一度選ばれるごとにが加算されるものとする。
数を回選んだ合計の最小値を求めよ。

制約

方針

priority queueを使う。
最小値をpriority queueから取り出してansに加算し、をpriority queueに入れる。これを繰り返す。

解答

Submission #4081765 - CODE THANKS FESTIVAL 2017(Parallel) | AtCoder

#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)
#define fi first
#define se second
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll N, K;
	cin >> N >> K;
 
	ll a[N], b[N];
	rep(i, N) cin >> a[i] >> b[i];
 
	priority_queue<pll, vector<pll>, greater<pll> > que;
	rep(i, N) que.push((pll){a[i], i});
 
	ll ans = 0;
	rep(i, K){
		pll x = que.top();
		que.pop();
		ans += x.fi;
		que.push((pll){x.fi + b[x.se], x.se});
	}
 
	cout << ans << endl;
}