2020NOI在线测试题解之--文具订购


前两天CCF举行了NOI在线测试,分为入门组和提高组。有不少同学吐槽说这些题难度太大,与去年CSP-J/S考试相比较要难很多。

其实,学员们这个感受是对的,因为这个测试是NOI,是全国赛,去年的CSP-J/S对应的是NOIP,是省赛。这么说吧:以前,那都是各省NOIP省一的获得者才有可能参加全国的NOI比赛的,所以,难度自然不一般。

第一题(文具订购)是酱紫的:

 

文具订购 

【题目描述】

 

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

 

【题解】最容易想到的是暴力枚举,按购买原则1要求把n元钱刚好用光,那就枚举出所有刚好花光这n元钱的购买方案,然后再去按原则2和原则3来挑出最优解,当然,如果按原则1刚好花完n元钱的方案都不存在,那就肯定是没有购买方案了。

以样例2为例,n=14,拿到14元的情况下,我们可以枚举出:

0 2 2

1 1 1

这是所有刚好把n元钱花完的方案,其中,按条件2:成套的数量应尽可能大,因此1 1 1这个方案更优。

同样,对于任意的n,我们都可以采取暴力枚举的方法,假设7元钱的圆规购买0个、1个、2个直到n元钱全部用来购买圆规;在圆规的数量已假定的情况下,对4元钱的笔的数量进行枚举:0,1,2直到购买完圆规之后剩余的钱全部用来买笔;对于3元钱的笔记本,则不需要枚举了,因为一旦圆规和笔的数量已假定,剩余的钱也就确定了,只需要看剩余的钱是否是3的倍数(也即是否能购买整数个的3元钱笔记本就可以了),如果能,就说明这是一个潜在的方案。

在上述枚举情况下,同步根据原则2和原则3来确定最优解即可。

下面给出主要的代码:

 

这道题看似得到了完美的求解,但是,可惜,当n达到本题要求的最大规模100000时,求解过程会超时,因为按这个暴力枚举的算法,本题的时间复杂度是接近O(n*n)的,因此应该找到更优的解法,或者对上述的枚举过程进行优化。

为了找出规律,不妨让n分别为1,2,3,......100元时,打印出结果来观察:

-1

-1

0 0 1

0 1 0

-1

0 0 2

0 1 1

0 2 0

0 0 3

0 1 2

0 2 1

0 0 4

0 1 3

1 1 1

0 0 5

0 1 4

1 1 2

1 2 1

0 1 5

1 1 3

1 2 2

1 3 1

1 1 4

1 2 3

1 3 2

1 1 5

1 2 4

2 2 2

1 1 6

1 2 5

2 2 3

2 3 2

1 2 6

2 2 4

2 3 3

2 4 2

2 2 5

2 3 4

2 4 3

2 2 6

2 3 5

3 3 3

2 2 7

2 3 6

3 3 4

3 4 3

2 3 7

3 3 5

3 4 4

3 5 3

3 3 6

3 4 5

3 5 4

3 3 7

3 4 6

4 4 4

3 3 8

3 4 7

4 4 5

4 5 4

3 4 8

4 4 6

4 5 5

4 6 4

4 4 7

4 5 6

4 6 5

4 4 8

4 5 7

5 5 5

4 4 9

4 5 8

5 5 6

5 6 5

4 5 9

5 5 7

5 6 6

5 7 5

5 5 8

5 6 7

5 7 6

5 5 9

5 6 8

6 6 6

5 5 10

5 6 9

6 6 7

6 7 6

5 6 10

6 6 8

6 7 7

6 8 6

6 6 9

6 7 8

6 8 7

6 6 10

6 7 9

7 7 7

6 6 11

容易发现:只有当n等于1,2,5这三种情况下,不存在购买方案,其余所有数值都是存在最优解的,而且最优解中,三个数字比较接近(毕竟要满足条件2嘛),为了验证这一点,我们可以试着让n=1000,1001,1002...1099,再观察一下这100个结果:

71 71 73

71 72 72

71 73 71

71 71 74

71 72 73

71 73 72

71 71 75

71 72 74

72 72 72

71 71 76

71 72 75

72 72 73

72 73 72

71 72 76

72 72 74

72 73 73

72 74 72

72 72 75

72 73 74

72 74 73

72 72 76

72 73 75

73 73 73

72 72 77

72 73 76

73 73 74

73 74 73

72 73 77

73 73 75

73 74 74

73 75 73

73 73 76

73 74 75

73 75 74

73 73 77

73 74 76

74 74 74

73 73 78

73 74 77

74 74 75

74 75 74

73 74 78

74 74 76

74 75 75

74 76 74

74 74 77

74 75 76

74 76 75

74 74 78

74 75 77

75 75 75

74 74 79

74 75 78

75 75 76

75 76 75

74 75 79

75 75 77

75 76 76

75 77 75

75 75 78

75 76 77

75 77 76

75 75 79

75 76 78

76 76 76

75 75 80

75 76 79

76 76 77

76 77 76

75 76 80

76 76 78

76 77 77

76 78 76

76 76 79

76 77 78

76 78 77

76 76 80

76 77 79

77 77 77

76 76 81

76 77 80

77 77 78

77 78 77

76 77 81

77 77 79

77 78 78

77 79 77

77 77 80

77 78 79

77 79 78

77 77 81

77 78 80

78 78 78

77 77 82

77 78 81

78 78 79

78 79 78

77 78 82

78 78 80

78 79 79

果然,最优购买方案中,最小值与最大值之间相差并不大,这给我们一个启示,我们在枚举时,其实是有机会大大缩小这个枚举范围的。

显然,我们的枚举起点,可以考虑从n/14向下取整的结果减去1的位置开始(当然,如果n<14时可以就不需要减1了),因为,如果购买完成套的三种物品后,如果还存在余数,那么只需要让7元的圆规少买一个,就可以凑到购买完整的笔和笔记本的钱了(想想为什么?)

代码按上述优化的思路进行修改后,对于100000这样的数据规模已经可以轻松解决了。(不过,其实还可以进一步减小枚举的数量,那就是枚举的最大值,也不需要到达将n元钱全部用来购买7元的圆规这种地步,这个留给读者朋友去优化吧。)


附:文本格式的代码:

void solve1(){

int n1,n2,n3,max_min=-1, sum=0;

int start = n/14 - 1;

if(start<0) start = 0;

for(int i=start; 7*i<=n; i++){ //从start的位置开始枚举

for(int j=start; j*4+i*7<=n; j++){

int rest = n - i*7 - j*4;

if(rest>=0 && rest%3 == 0){ //剩余的钱是3的倍数

int k = rest/3;

int num = min(min(i,j),k);

//根据原则2 和原则3 选取最优方案

if(num>max_min || (num==max_min && (i+j+k)>sum)){

max_min = num;

sum = i+j+k;

n1 = i;

n2 = j;

n3 = k;

}

}

}

}

if(max_min == -1) cout<<"-1"<<endl;

else cout<<n1<<" "<<n2<<" "<<n3<<endl;

}

客服电话:400-901-1094
周一至周日 9:00-23:00
联系邮箱 : 4009011094@docoding.net
微信公众号
微博
豆蔻丁DoCoding
COPYRIGHT © 2019 南京豆蔻丁信息科技有限公司版权所有 | 苏ICP备19004048号