srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

aoj 0567 - Best Pizza

問題

問題概要

条件に合う最もよいピザを選ぶ

解法

この問題は貪欲法で解ける。なぜなら、トッピングの値段がすべて同じだからである。トッピングの値段が同じであるなら、トッピングのカロリーが高いものから優先的に選んでいけばいい。あとは、何個のトッピングを選ぶ時が最適解なのかわからないので、それを全探索すればいい。トッピングを選ぶ数を0~n個として、カロリーの高いものから順に選んですべての場合の カロリー/値段を計算して一番大きいものを答えとして出力すればいい。

ミス

dp臭がすごかった。たぶんdpでもできるのでdpで解きたい。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

//貪欲法で解ける
int main(void){
    int n, a, b;
    double kizi;
    cin >> n >> a >> b >> kizi;
    vector<int> debu(n + 1);//カロリーを入れる配列
    rep(i, n) cin >> debu[i];
    sort(debu.begin(), debu.end());
    reverse(debu.begin(), debu.end());//大きいものから並べる
    vector<double> ans(n + 1);
    //カロリーが高いものから優先的に選んでいく
    rep(i, n + 1){//i個のトッピングを選ぶとき
        double nedan = (double)a + (double)i * (double)b;//値段の計算
        double karori = kizi;//生地のカロリーを初期値とする
        rep(j, i) karori += debu[j];//i個のトッピングをカロリーの高いものから優先的にi個選んでいる
        ans[i] = karori / nedan;//答えを入れておく
    }
    sort(ans.begin(), ans.end());
    reverse(ans.begin(), ans.end());
    printf("%d\n", (int)floor(ans[0]));//一番大きいものを出力
    return 0;
}