Bake Breads

2 secs 1024 MB

dyktr_06

問題

提出

テストケース

解説

この問題の制約だと、 $N$ の大きさが最大でも $8$ と少ないのでオーブンに入れる順番を全探索することができます。

入れる順番が決まったら、優先度付きキューなどのデータ構造を用いることによって愚直にシミュレートが可能です。

以下の実装例の場合は、計算量は $O(N・N! \log N)$ です。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

const long long INF = 0x1fffffffffffffff;

int main(){
    int n, k;
    cin >> n >> k;
    vector<long long> t(n);
    for(int i = 0; i < n; i++){
        cin >> t[i];
    }
    long long ans = INF;
    do{
        long long now = 0;
        priority_queue<long long, vector<long long>, greater<long long>> q;
        for(int i = 0; i < n; i++){
            if((int) q.size() < k){
                q.push(t[i]);
            }else{
                long long v = q.top();
                q.pop();
                now = v;
                q.push(t[i] + now);
            }
        }
        while(q.size()){
            now = q.top();
            q.pop();
        }
        ans = min(ans, now);
    }while(next_permutation(t.begin(), t.end()));
    cout << ans << endl;
}