【Codeforces 478C】Table Decorations

给你r,g,b三种颜色的气球每张桌子要放3个气球但是3个气球的颜色不能全都一样 (允许两个一样,或者全都不一样) 问你最多能装饰多少张桌子

【题解】

先把每张桌子都装饰上 a,b,c三种不同颜色的气球 (显然这样的桌子最多为Math.min(r,g,b)张) 然后把气球的个数减掉这种方法设置为ABC 然后肯定只剩两种气球还可能有剩余那么就用其中数量比较多的一种放2个,比较少的放1个(也是贪心,但不一定对) 这种方法定义为AAB 然后再减少A,B的数量此后有两种情况 ①A还剩很多,B已经没了那么我们就用剩余的A去和"ABC"方案中的B或者C替换一下(替换谁都无所谓,只要不是A就行) 这样就可能再凑出来一组"AAB"或者"AAC" 所以方案还可以加上min(restA/3,num("AAB") ); ②A只剩1个或0个(因为是减去*2),B还有很多如果A剩一个,B还有2个以上那么可以凑出来一个"ABB",ans++,然后A=0,b-=2 然后就变成A剩0个,B还有很多的情况这个时候我们可以用B去替换我们上面定义的"ABC"中的A或者上面定义的"AAB"中的A(①中因为是A剩余,但是A如果替换的话,就不符合题意了,但是B可以替换) 因此答案再累加对应的数量就好

【代码】

import java.io.*;
import java.util.*;

public class Main {
	
	
	static InputReader in;
	static PrintWriter out;
		
	public static void main(String[] args) throws IOException{
		//InputStream ins = new FileInputStream("E:\rush.txt");
		InputStream ins = System.in;
		in = new InputReader(ins);
		out = new PrintWriter(System.out);
		//code start from here
		new Task().solve(in, out);
		out.close();
	}
	
	static int N = (int)1e6;
	static class Task{
		public void solve(InputReader in,PrintWriter out) {
			int r,g,b;
			int []a = new int[3];
			for (int i = 0;i < 3;i++) a[i] = in.nextInt();
			Arrays.sort(a, 0,3);
			int ans = a[0];
			int g1 = ans;
			for (int i = 1;i < 3;i++) a[i]-=a[0];
			int temp = Math.max(a[1], a[2]);
			int temp1 = Math.min(a[1], a[2]);
			
			int g2 = Math.min(temp/2, temp1);
			ans = ans + g2;
			
			temp = temp - g2*2;temp1-=g2;
			if (temp1==0) {
				//temp1变成0,temp可能会有剩余
				int g3 = Math.min(temp/3, g1);
				ans = ans + g3;
				temp = temp-g3*3;
			}else {
				//temp没有那么多了,temp1还有剩余
				if (temp!=0) {
					//temp==1
					temp--;
					if (temp1>=2) {
						ans++;
						temp1-=2;
					}
				}
				
				//temp变成0了,temp1还可能有剩余和之前3个3个的换一下
				int g3 = Math.min(temp1/3, g1);
				temp1 = temp1-g3*3;
				ans += g3;
				int g4 = Math.min(temp1/3, g2);
				temp1 = temp1-g4*3;
				ans = ans + g4;
			}
			out.println(ans);
		}
	}

	

	static class InputReader{
		public BufferedReader br;
		public StringTokenizer tokenizer;
		
		public InputReader(InputStream ins) {
			br = new BufferedReader(new InputStreamReader(ins));
			tokenizer = null;
		}
		
		public String next(){
			while (tokenizer==null || !tokenizer.hasMoreTokens()) {
				try {
				tokenizer = new StringTokenizer(br.readLine());
				}catch(IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
	}
}