Round #326 A. Duff and Meat｜Codeforces

Problem - A - Codeforces を解きました。
ktnさんに適度な問題をいくつかpick upして頂いたのですがそのうちの1問です。
(適度な問題：私のレベルに対しての適度)

Duffちゃんが必要な肉の量/day と コスト/day がN日分与えられるので、
必要な肉を買う最小コストをprintすると言うもの(適当)
つまり特売日に肉を買いだめて行くスタイル。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> amount(N),cost(N);
	REP( i, N )
	{
		cin >> amount[i] >> cost[i];
	}
	int MIN = cost.front(),res{};
	REP( i, N )
	{
		MIN = min( MIN, cost[i] );
		res += amount[i] * MIN;
	}
	cout << res << endl;
	return 0;
}

最終的に修正したコード。
最初、min値の更新を if に入れたり変なことをしていた...。
でも簡単な貪欲問題解けて良かった！
その時々で最善な選択をしていく、が貪欲と呼ばれる解法っぽいです。

#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
using namespace std;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	vector<int> amount(N), cost(N);
	REP( i, N )
	{
		cin >> amount[i] >> cost[i];
	}
	vector<int> total;
	partial_sum( cost.begin(), cost.end(), back_inserter(total),
		[]( int MIN, int cost ){ return min( MIN, cost ); } );
	cout << inner_product( amount.begin(), amount.end(), total.begin(), 0 ) << endl;
	return 0;
}

次にプロのコードからの学び。
使った事のないSTLが2つも出て来たので学習的でした。
std::partial_sum は要素の部分和が取れます*1。
が、その機能を利用して第四引数のラムダでmin値をreturnしています。
(※部分和を取る訳ではない / ここの理解が難しかった...)

「先頭から各位置までの要素全ての和」の代わりに
「先頭から各位置までの要素全ての min」を求めている

その後、要素間を乗算し加算されたtotalを返してくれる、
std::inner_product*2 を使って計算結果を得ます。

STLを使ったこんな書き方も出来るんだー...という学びでした。

(難しかった....)

*1:partial_sum - cpprefjp C++日本語リファレンス

*2:inner_product - cpprefjp C++日本語リファレンス