题目链接:http://codeforces.com/problemset/problem/322/B
题目意思:给定红花、绿花和蓝花的朵数,问组成四种花束(3朵红花,3朵绿花,3朵蓝花,1朵红花+1朵绿花+1朵蓝花)的总数最大为多少。
一开始以为是水题,其实很多情况都没有考虑到,反反复复修改终于过了。
其实要考虑两种情况,这两种情况较好的那种就是最优解。姑且把四种花束分为两种类型:清一色型(3朵红,3朵绿,3朵蓝)和混杂型(红绿蓝各一朵)。
第一种情况就是,保证清一色型最多(3种花都要除以3),能组成混杂型的朵数是剩下所有没使用的花中最少的那个余数;第二种情况是混杂型最多(此时三种花中最大的那个余数),清一色型的数目为剩下三种花中各除以3的总和。
需要特别注意的情况是,如果其中一种花色的数目为0但是其余两种花色至少一种多于3(此时可以全部用来做清一色花束)或者三种花色的数目都不为0但是每种的数目都少于3(此时全部用来做混合型花束)。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 using namespace std; 5 6 #define max(a, b) ((a) > (b) ? (a) : (b)) 7 #define min(a, b) ((a) > (b) ? (b) : (a)) 8 9 int main() 10 { 11 int r, g, b, sum, sum1, jd, jd1; 12 13 while (scanf("%d%d%d", &r, &g, &b) != EOF) 14 { 15 sum1 = sum = 0; 16 jd = min(r, min(g, b)); 17 jd1 = max(r, max(g, b)); 18 if (jd || jd1 >= 3) // 如果同时满足至少有一种花数目为0和最多的那一种花数目少于3,此时两种类型的花束都不能构成 19 { 20 sum1 = r/3 + g/3 + b/3; // 保证清一色型最多 21 if (min(r - r/3*3, min(g - g/3*3, b - b/3*3)) >= 0) // 防止剩余花中出现负数 22 { 23 sum1 += min(r - r/3*3, min(g - g/3*3, b - b/3*3)); 24 sum = max(r%3, max(g%3, b%3)); // 保证混合色型花束最多 25 if (r-sum >= 0 && g-sum >= 0 && b-sum >= 0) 26 sum += (r-sum)/3 + (g-sum)/3 + (b-sum)/3; 27 } 28 } 29 printf("%d\n", max(sum, sum1)); 30 } 31 return 0; 32 }