【题目描述】

小明的班上共有n元班费，同学们准备使用班费集体购买3种物品。

1. 圆规，每个7元。

2. 笔，每支4元。

3. 笔记本，每本3元。小明负责订购文具，设圆规、笔、笔记本的订购数量为a,b,c,他订购的原则依次如下：

1.n元钱必须正好用光，即7a+4b+3c=n;
2.在满足以上条件的情况下，成套的数量尽可能大，即a,b,c中的最小值尽可能大。
3.在满足以上条件的情况下，物品的总数尽可能大，即a+b+c尽可能大。请你帮助小明求出满足条件的最优方案。可以证明若存在方案，则最优方案唯一。

【输入描述】

从文件order.in中读入数据。仅一行一个整数n表示班费数量。

【输出描述】

输出到文件order.out中。若方案不存在则输出-1.否则输出一行三个用空格分隔的非负整数a,b,c表示答案。

【输入样例1】

1

【输出样例1】

-1

【输入样例2】

14

【输出样例2】

1 1 1

【输入样例3】

33

【输出样子3】

1 2 6

【样例3解释】

a=2,b=4,c=1 也是满足条件1，2的方案，但是对于条件3，该方案只买了7个物品，不如a=1,b=2,c=6的方案。

【数据范围】

对于测试点1~6：n<=14。对于测试点7~12：n是14的倍数。对于测试点13~18：n<=100。对于所有测试点：0<=n<=10⁵

【限制】

时间1.0s 、空间限制256MB。

【题目分析】

• 最简单的方法是暴力枚举，也可以使用DP

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

int n;

int main(void) {

	cin>>n;

	if(n == 0) { //特判
		cout<<"0 0 0"<<endl;
		return 0;
	}

	for(int p=n/14; p>=0; p--) { //枚举最小值，也就是a的个数
		for(int j=p; j<=n/4; j++) //枚举b
			for(int k=p; k<=n/3; k++) //枚举c
				if(p*7+j*4+k*3 == n) { //如果有解
					cout<<p<<" "<<j<<" "<<k<<endl;
					return 0;//输出，结束程序
				}
	}
	cout<<"-1"<<endl;//无解输出-1
	return 0;//完美AC~
}

#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,ans=0;//ans用来记录套数
	cin>>n;
	if(n==0) { //若n=0，则直接输出答案；
		cout<<0<<" "<<0<<" "<<0;
		return 0;
	}
	if(n<6 && n!=4 && n!=3) { //若n无法分完，则直接输出答案；
		printf("-1");
		return 0;
	}
	ans=n/14;
	n%=14;//本代码的核心部分（个人觉得），求套数
	if(n<6 && n!=4 && n!=3 && n!=0)
		ans--,n+=14;//若在套数最多时n分不完，套数-1；
	if(n==0) { //若正好分完，直接输出三个套数
		cout<<ans<<" "<<ans<<" "<<ans<<endl;
		return 0;
	}
	//准备，最长if特判就要来了：
	if(n==3) {
		cout<<ans<<" "<<ans<<" "<<ans+1<<endl;
		return 0;
	}
	if(n==4) {
		cout<<ans<<" "<<ans+1<<" "<<ans<<endl;
		return 0;
	}
	if(n==6) {
		cout<<ans<<" "<<ans<<" "<<ans+2<<endl;
		return 0;
	}
	if(n==7) {
		cout<<ans<<" "<<ans+1<<" "<<ans+1<<endl;
		return 0;
	}
	if(n==8) {
		cout<<ans<<" "<<ans+2<<" "<<ans<<endl;
		return 0;
	}
	if(n==9) {
		cout<<ans<<" "<<ans<<" "<<ans+3<<endl;
		return 0;
	}
	if(n==10) {
		cout<<ans<<" "<<ans+1<<" "<<ans+2<<endl;
		return 0;
	}
	if(n==11) {
		cout<<ans<<" "<<ans+2<<" "<<ans+1<<endl;
		return 0;
	}
	if(n==12) {
		cout<<ans<<" "<<ans<<" "<<ans+4<<endl;
		return 0;
	}
	if(n==13) {
		cout<<ans<<" "<<ans+1<<" "<<ans+3<<endl;
		return 0;
	}
	if(n==15) {
		cout<<ans<<" "<<ans<<" "<<ans+5<<endl;
		return 0;
	}
	if(n==16) {
		cout<<ans<<" "<<ans+1<<" "<<ans+4<<endl;
		return 0;
	}
	if(n==19) {
		cout<<ans<<" "<<ans+1<<" "<<ans+5<<endl;
		return 0;
	}
	//是的，这样就没了（亲测，可以AC）
	return 0;
}