当前位置:首页 > 题解目录 > 正文内容

文具订购(NOI online入门组)

亿万年的星光4年前 (2021-04-09)题解目录1783

【题目描述】

小明的班上共有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;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】合并有序表

【题目描述】k路归并问题把k个有序表合并成一个有序表。元素共有n个。【输入描述】读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数,表示第i个序列。总数小于100000。【输出描述】输...

【题解】电缆线(2019青岛市程序设计竞赛)

【问题描述】在郊区有N座通信基站,P条双向电缆,第 i 条电缆连接基站 A_i 和 B_i。特别地,1号基站是通信公司的总站,N号基站位于一座农场中。现在,农场主希望对通信线路进行升级,其中升级第 i...

【题解】合根植物

【题解】合根植物

【题目描述】w星球的一个种植园,被分成 m * n 个小格子(东西方向m行,南北方向n列)。每个格子里种了一株合根植物。这种植物有个特点,它的根可能会沿着南北或东西方向伸展,从而与另一个格子的植物合成...

【题解】给定和为定数

【题目描述】给出若干个整数,询问其中是否有一对数的和等于给定的数。【输入描述】第一行是整数n(0 < n ≤ 100,000),表示有n个整数。第二行是n个整数。整数的范围是在0到108之间。第...

数列

数列

【题目描述】有一个分数序列求出这个序列的前n项和,结果保留两位小数。(注意,不用通分,单项相加即可)【输入描述】一个数字,N【输出描述】前N项的和【样例输入】10【样例输出】16.48【题目分析】(1...

【题解】钟神赛车

【题目描述】钟神近来编码劳累,想骑车风光一番,于是找某君骑自行车比赛。已知某君和钟神的每辆自行车的速度,钟神赢一场得50银两银子,输一场赔50银两,平局不挣也不赔。钟神可以随意安排高中低档自行车的出场...