2059：【例3.11】买笔

行路难，行路难，多歧路，今安在？
长风破浪会有时，直挂云帆济沧海。
【题目描述】
期末来临了，班长小Q决定将剩余班费x
元钱，用于购买若干支钢笔奖励给一些学习好、表现好的同学。已知商店里有三种钢笔，它们的单价为6元、5元和4元。小Q想买尽量多的笔（鼓励尽量多的同学），同时他又不想有剩余钱。请您编一程序，帮小Q制订出一种买笔的方案。

【输入】
一个正整数x（剩余班费）。

【输出】
一行，依次为6元、5元和4元钱笔的数目，用一个空格隔开。

【输入样例】
10
【输出样例】
1 0 1

#include<cstdio>#include<string>#include<iomanip>#include<cmath>#include<iostream>usingnamespacestd;intmain(){intn,a,b,c;cin>>n;if(n%4==0){a=0;b=0;c=n/4;}if(n%4==1){a=0;b=1;c=(n/4)-1;}if(n%4==2){a=1;b=0;c=(n/4)-1;}if(n%4==3){a=1;b=1;c=(n/4)-2;}cout<<a<<" "<<b<<" "<<c<<endl;return0;}

解题思路：贪心算法
初始分配：先将所有的钱xxx全部用来买4元的笔，可以买 c = x / 4 支，此时会剩下余数 r = x % 4 元。处理余数：根据余数 r 的不同情况，对已购买的4元笔进行“退货换购”来凑齐整钱：
如果 r = 0：正好花完，不需要调整。即：0支6元，0支5元，c 支4元。
如果 r = 1：剩下1元买不了任何笔。我们可以退掉1支4元笔，这样手里就有4+1=54 + 1 = 54+1=5元，刚好可以换购1支5元的笔。即：0支6元，1支5元，c - 1 支4元。
如果 r = 2：剩下2元。退掉1支4元笔，手里有4+2=64 + 2 = 64+2=6元，刚好换购1支6元的笔。即：1支6元，0支5元，c - 1 支4元。
如果 r = 3：剩下3元。退掉2支4元笔，手里有8+3=118 + 3 = 118+3=11元，刚好换购1支6元和1支5元的笔。即：1支6元，1支5元，c - 2 支4元。