c++ - How can I optimise this to run in an efficient manner? -
the link question follows: http://codeforces.com/problemset/problem/478/c
you have r red, g green , b blue balloons. decorate single table banquet need 3 balloons. 3 balloons attached table shouldn't have same color. maximum number t of tables can decorated if know number of balloons of each color?
your task write program given values r, g , b find maximum number t of tables, can decorated in required manner.
input: single line contains 3 integers r, g , b (0 ≤ r, g, b ≤ 2·10^9) — number of red, green , blue baloons respectively. numbers separated 1 space.
output: print single integer t — maximum number of tables can decorated in required manner.
so, did was, in greedy manner, searched maximum , minimum value each time , subtracted 2 , 1 respectively if possible. here code:
int main (void) { int ans=0,r,g,b; cin>>r>>g>>b; while (1) { int a1 = maxfind(r,g,b); int a2 = minfind(r,g,b); //ans++; if (a1 >= 2 && a2 >= 1) { ans++; if (indma == 1) r = r-2; else if (indma == 2) g = g-2; else b = b-2; if (indmi == 1) r = r-1; else if (indmi == 2) g = g-1; else b = b-1; } else if (r == 1 && g == 1 && b == 1) { ans++; break; } else break; } cout<<ans<<"\n"; int maxfind(int r, int g, int b) { indma = 0; int temp = int_min; if (r >= temp) { temp = r; indma = 1; } if (g >= temp) { temp = g; indma = 2; } if (b >= temp) { temp = b; indma = 3; } return temp; }
similar function findmin
, make sure it's not same number chosen in case maximum , minimum values same. however, since limit 2*10^9, obviously, surpasses time limit. how can optimise it? thanks!
edit: can find sample test cases in link question. however, still adding 1 of them.
input 5 4 3 output 4
explanation: in first sample can decorate tables following balloon sets: "rgg", "gbb", "brr", "rrg", "r", "g" , "b" represent red, green , blue balls, respectively.
you can split problem 2 scenarios, either use balloons(with 0, 1, or 2 left over), or don't because there many of 1 color , not enough of other two.
if use balloons, answer (r+g+b)/3
if don't use balloons, answer equal sum of lower 2 of 3 numbers.
t = min((r+g+b)/3,r+g+b-max(r,g,b))
Comments
Post a Comment