题解：P6775 [NOI2020] 制作菜品

chrisgr · 2024-11-22 19:53:47 · 题解

m \ge n - 1

对于这种情况我们有一个显而易见的贪心，设数量最少的原料为第 i 个，数量最多的原料为第 j 个。如果 d_i \ge k 我们直接将其做成一道菜，否则我们将 d_i 全部用作一道菜，同时在这道菜中加入 d_j 的一部分，使得其符合要求。

首先先证明一下贪心的正确性，将 d 数组排序，假设不存在 d_1 + d_n > k。
即假设 d_1 + d_n \le k。
因为 d 为正整数，那么 d_n < k。
就有 \sum\limits_{i = 2}^{n - 1} d_i < (n - 2) \cdot k。
那么 \sum\limits_{i = 1}^{n} d_i < (n - 1) \cdot k。
因为 \sum\limits_{i = 1}^{n} d_i = m \cdot k 与 m \ge n - 1。
所以 \sum\limits_{i = 1}^{n} d_i \ge (n - 1) \cdot k。
与先前算的结果矛盾，所以假设不成立，在 m \ge n - 1 时一定存在 d_1 + d_n > k 同时因为二者相加严格大于 k 所以每次贪心后，两个原料一定还会剩下至少一部分，所以最劣情况也只会 m - 1 同时 n - 1 不会在贪心过程中出现 m < n - 1 的情况。

m = n - 2

对于这种情况，我们容易发现如果还按贪心做法，最终可能会出现 m = 1 同时 n = 3 的情况，方案不合法，所以我们需要考虑将 m = n - 2 的情况转化为 m = n - 1 的情况。
注意到当 m = n - 2 时，可以将 m 和 n 分解为 m_1 = n_1 - 1 和 m_2 = n_2 - 1 那么只要我们对 d 进行可行性背包，看是否可以将 d 分为上述的两部分，并使用 bitset 优化，就可以通过本题了。

题解还没通过，口胡一个证明吧。
首先这个充分性肉眼可见，所以只需要证明必要性。
假设 m = n - 2 分不出来两部分。
那么第一种情况 m = n - 2 无法拆分，那么容易证明此时一定没有合法解（拆不出两部分说明，没有一道菜可以同时消耗掉两种原料，那么每次做菜只会使 m - 1 同时 n - 1 最后一定存在 m = 1 同时 n = 3 的情况）。
第二种情况，我们可以分出 m_1 > n_1 - 1 和 m_2 < n_2 - 1 两个部分，对于第一部分肯定有解，第二部分肉眼可见无法拆分为 m_1' \ge n_1' - 1 与 m_2' \ge n_2' - 1 两部分，所以必然存在不可分，或一部分 m < n - 1 此时对于前者可以归类为第一种情况的证明，对于后者我们递归划分 m < n - 1 的部分最后必然会出现不可分，或分出 m = 1 同时 n = 3 的情况，两种情况都不合法，所以第二种情况不合法（感觉没啥问题轻喷）。

题解还没过，来聊聊时间复杂度吧挤牙膏写法。
首先，贪心就算写的再丑陋也不是时间复杂度的大头（我写的是 \mathcal{O}(n \log n) ）所以我们来分析一下背包的时间复杂度吧。很明显没有优化的时候，背包的时间复杂度是 \mathcal{O}(n^2 \cdot k) 这个时间复杂度明显只能过前 17 个点，所以我们对其优化，之后时间复杂度为 \mathcal{O}(\frac{ n^2 \cdot k}{w}) 稳稳通过本题。

小细节：背包时有可能溢出，所以需要多开一点，并且初始化的值应该在中间。

CODE

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int n, m, k, d[N];
bool book[N];
bitset<5000004>bag[N], kk;
void dfs(int x, int y) {
    if(!y) return;
    else if(!bag[x + 1][2500000 + y]) book[x] = 1, dfs(x + 1, y - d[x]);
    else dfs(x + 1, y);
}
struct node{ int id, d; };
bool operator <(const node & x, const node & y) { 
    if(x.d ^ y.d) return x.d < y.d;
    else return x.id < y.id;
}
int main() {
    //freopen("dish2.in", "r", stdin);
    //freopen("1.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--) {
        //cout << t << endl << endl;
        scanf("%d%d%d", &n, &m, &k);
        for(int i = n; i; --i) scanf("%d", d + i);
        if(m == n - 2) {
            if(m == 3) {
                puts("-1");
                continue;
            }
            memset(book, 0, sizeof(book));
            int dd[N];
            for(int i = n; i; --i) {
                dd[i] = d[i];
                d[i] = k - d[i];
            }
            bag[n + 1][2500000] = 1, kk = 0, kk[2500000 + k] = 1;
            //cout << kk << endl;
            for(int i = n ; i; --i) {
                bag[i] = bag[i + 1] | (d[i] >= 0 ? bag[i + 1] << d[i] : bag[i + 1] >> -d[i]);
                //if(t == 5) cout << i << "  " << bag[i][k] << endl;
            }
            if((bag[1] & kk) == 0) {
                puts("-1");
                continue;
            }
            dfs(1, k);
            multiset<node> lc1, lc2;
            for(int i = n; i; --i) {
                if(book[i]) lc1.insert({n - i + 1, dd[i]});
                else lc2.insert({n - i + 1, dd[i]});
            }
            while(!lc1.empty()) {
                auto a = lc1.begin();
                node aa = *a;
                lc1.erase(a);
                printf("%d %d", aa.id, aa.d);
                if(aa.d < k) {
                    auto b = --lc1.end();
                    node bb = *b;
                    lc1.erase(b);
                    int bbb = k - aa.d;
                    printf(" %d %d", bb.id, bbb);
                    bb.d -= bbb;
                    if(bb.d) lc1.insert(bb);
                }
                putchar('\n');
            } while(!lc2.empty()) {
                auto a = lc2.begin();
                node aa = *a;
                lc2.erase(a);
                printf("%d %d", aa.id, aa.d);
                if(aa.d < k) {
                    auto b = --lc2.end();
                    node bb = *b;
                    lc2.erase(b);
                    int bbb = k - aa.d;
                    printf(" %d %d", bb.id, bbb);
                    bb.d -= bbb;
                    if(bb.d) lc2.insert(bb);
                }
                putchar('\n');
            } 
        } else {
            multiset<node> st;
            for(int i = n; i; --i) st.insert({n - i + 1, d[i]});
            while(!st.empty()) {
                auto a = st.begin();
                node aa = *a;
                st.erase(a);
                if(aa.d >= k) {
                    printf("%d %d", aa.id, k);
                    if(aa.d ^ k) {
                        aa.d -= k;
                        st.insert(aa);
                    }
                } else {
                    auto b = --st.end();
                    node bb = *b;
                    st.erase(b);
                    int bbb = k - aa.d;
                    printf("%d %d %d %d", aa.id, aa.d, bb.id, bbb);
                    bb.d -= bbb;
                    if(bb.d) st.insert(bb);
                }
                putchar('\n');
            }
        }
    }
    return 0;
}