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

Popular posts from this blog

resizing Telegram inline keyboard -

command line - How can a Python program background itself? -

php - "cURL error 28: Resolving timed out" on Wordpress on Azure App Service on Linux -