题目描述

如题

算法

(暴力枚举) $O(n^2)$

用n方的方法枚举圆规和笔的个数，算出笔记本的个数，再进行判断这个方案是否可行。

C++ 代码

#include <cstdio>
#include <iostream>
using namespace std;

int n, mi, ma, x, y, z; //mi表示三种物品最多能成多少套，ma表示三种物品的总数最大是多少

int Min(int a, int b, int c) { //Min是求三个数的最小值
    return min(min(a, b), c);
}

int main() {

    scanf("%d", &n);

    if (n == 1 || n == 2 || n == 5 || n == 6) {//这4种情况都是没有合法方案的
        printf("-1");
        return 0;
    }

    for (int i=0; i<=n/7; i++) {//枚举圆规个数
        if (i < mi) continue; //这里是小优化，如果圆规的个数是比三种物品最少能组成套数小，肯定无法更新答案

        for (int j=0; j<=(n-7*i)/4; j++) {//枚举笔有多少支
            if (j < mi) continue; //同上优化

            int k = (n-7*i-4*j) / 3;//通过i和j算出k
            if (k < mi) continue; //同上优化

            if (i * 7 + j * 4 + k * 3 != n) continue; //不满足条件1

            int s = Min(i, j, k); 

            if (s < mi) continue;

            // 如果这种方案的最小套数与mi相等，那么要判断三种物品的总数是否比ma大才更新答案，如果最小套数比mi大，直接更新ma和mi
            if (s == mi && (i + j + k) > ma || s > mi)  { 
                ma = i + j + k;
                mi = s;
                x = i, y = j, z = k;    
            }
        }
    }

    printf("%d %d %d", x, y, z);
    return 0;
}