#5#9#10总是tle呜呜呜
查看原帖
#5#9#10总是tle呜呜呜
628263
mengyacat楼主2021/11/28 22:17
#include <iostream>
#include<algorithm>
#include <cstdio>

using namespace std;

class CutWood {

public:

    int woods[51];
    int woodsNum;
    int needs[1001];
    int needsNum;
    int ans = 0;

    void input() {
        cin >> woodsNum;
        if(woodsNum==0)return;
        for (int i = 0; i < woodsNum; i++) {
            cin >> woods[i];
        }
        sort(woods, woods + woodsNum);
        cin >> needsNum;
        if(needsNum==0)return;
        for (int i = 0; i < needsNum; i++) {
            cin >> needs[i];
        }
        sort(needs, needs + needsNum);

    }

    bool isengugh(int wood) {
        for (int i = 0; i < woodsNum; i++) {
            if (woods[i] >= wood)
                return true;
        }
        return false;
    }

    void output() const {
        cout << ans << endl;
    }

    void f(int left, int score = 0) {

        ans = max(score, ans);
        while (!isengugh(needs[needsNum - left]))
            left -= 1;
        if (left == 0) {

            return;
        }
        if (score + left <= ans) {
            return;
        }

        for (int i = 0; i < woodsNum; i++) {

            if (woods[i] - needs[needsNum - left] >= 0) {
                woods[i] -= needs[needsNum - left];
                f(left - 1, score + 1);
                woods[i] += needs[needsNum - left];

            }

        }
        //f(left - 1, score);

    }


};

int main() {
    auto *c = new CutWood();
    c->input();

    c->f(c->needsNum, 0);
    c->output();


}
2021/11/28 22:17
加载中...