2059：【例3.11】买笔

行路难行路难多歧路今安在长风破浪会有时直挂云帆济沧海。【题目描述】期末来临了班长小Q决定将剩余班费x元钱用于购买若干支钢笔奖励给一些学习好、表现好的同学。已知商店里有三种钢笔它们的单价为6元、5元和4元。小Q想买尽量多的笔鼓励尽量多的同学同时他又不想有剩余钱。请您编一程序帮小Q制订出一种买笔的方案。【输入】一个正整数x剩余班费。【输出】一行依次为6元、5元和4元钱笔的数目用一个空格隔开。【输入样例】10【输出样例】1 0 1#includecstdio#includestring#includeiomanip#includecmath#includeiostreamusingnamespacestd;intmain(){intn,a,b,c;cinn;if(n%40){a0;b0;cn/4;}if(n%41){a0;b1;c(n/4)-1;}if(n%42){a1;b0;c(n/4)-1;}if(n%43){a1;b1;c(n/4)-2;}couta b cendl;return0;}解题思路贪心算法初始分配先将所有的钱xxx全部用来买4元的笔可以买 c x / 4 支此时会剩下余数 r x % 4 元。处理余数根据余数 r 的不同情况对已购买的4元笔进行“退货换购”来凑齐整钱如果 r 0正好花完不需要调整。即0支6元0支5元c 支4元。如果 r 1剩下1元买不了任何笔。我们可以退掉1支4元笔这样手里就有4154 1 5415元刚好可以换购1支5元的笔。即0支6元1支5元c - 1 支4元。如果 r 2剩下2元。退掉1支4元笔手里有4264 2 6426元刚好换购1支6元的笔。即1支6元0支5元c - 1 支4元。如果 r 3剩下3元。退掉2支4元笔手里有83118 3 118311元刚好换购1支6元和1支5元的笔。即1支6元1支5元c - 2 支4元。