torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces 160, Division 2, C : Maxim and Discounts

概要

n 個の品物を購入したい。
今この店では割引セールをやっており、m 個あるバスケットのいずれかに q_i 個丁度の商品を入れることで、二個までの商品を無料にすることができる。
ただし、無料にできるのはバスケットに入ってる最も安い商品の金額を超えない商品のみである。
n 個の品物を全て購入するのに必要な金額の最小値を求めよ。

解法

できるだけ小さいバスケットを使うことで、割引できる商品を増やすことができます。
また、最も高い品物はどうやっても割引できません。
更に、最も高い品物を除いた商品集合の内でも、最も高い品物は割引できません。
従って、値段の高い商品から順に詰める Greedy となります。

コード

typedef long long LL;
typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define EACH( v, c ) for ( auto &v : c )

#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int m;
	cin >> m;

	VI qs( m );
	EACH( q, qs )
	{
		cin >> q;
	}

	int n;
	cin >> n;

	VI as( n );
	EACH( a, as )
	{
		cin >> a;
	}

	int q = *min_element( ALL( qs ) );
	sort( ALL( as ), greater<int>() );

	LL res = 0;

	for ( int i = 0; i < as.size(); i += q + 2 )
	{
		REP( j, i, min( i + q, (int)as.size() ) )
		{
			res += as[j];
		}
	}

	cout << res << endl;

	return 0;
}