【题目描述】

小明的班上共有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<=105

【限制】

时间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;  }

(adsbygoogle = window.adsbygoogle || []).push({});