URAL 1200 Horns and Hoofs 枚举

设horns和hoofs的数量分别为 x 和 y ，题目要求：

满足 x+y <= K，使得A*x + B*y - x*x - y*y 最大。

枚举 i 从0~K，直接解方程得对称轴 x = ( 2*i + A - B ) / 4，判断对称轴是否在 [ 0, i ] 区间内。

注意：

1.精度

2.x需要上下个取整一次

3.如果最大值都<=0，那么最大收益直接为 0 即可。

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <algorithm>
  6 
  7 const double eps = 1e-3;
  8 const double INF = 1e10;
  9 
 10 using namespace std;
 11 
 12 double A, B;
 13 int N;
 14 
 15 int dcmp( double a )
 16 {
 17     if ( fabs(a) < eps ) return 0;
 18     return a < 0 ? -1 : 1;
 19 }
 20 
 21 double cal( int x, int y )
 22 {
 23     return A*x + B*y -x*x - y*y;
 24 }
 25 
 26 int main()
 27 {
 28     while ( ~scanf( "%lf%lf", &A, &B ) )
 29     {
 30         scanf( "%d", &N );
 31         double ans = -INF;
 32         int ansX, ansY;
 33 
 34         for ( int i = 0; i <= N; ++i )
 35         {
 36             int tmp = floor(( 2 * i + A - B ) / 4.0) ;
 37             if ( tmp < 0 ) tmp = 0;
 38             else if ( tmp > i ) tmp = i;
 39 
 40             double tmpcal = cal( tmp, i - tmp );
 41             if ( dcmp( ans - tmpcal ) < 0 )
 42             {
 43                 ans = tmpcal;
 44                 ansX = tmp;
 45                 ansY = i - tmp;
 46             }
 47             else if ( dcmp( ans - tmpcal ) == 0 )
 48             {
 49                 if ( tmp < ansX )
 50                 {
 51                     ansX = tmp;
 52                     ansY = i - tmp;
 53                 }
 54                 else if ( tmp == ansX )
 55                 {
 56                     if ( ansY > i - tmp )
 57                     {
 58                         ansY = i - tmp;
 59                     }
 60                 }
 61             }
 62 
 63             tmp = ceil( ( 2 * i + A - B ) / 4.0 ) ;
 64 
 65             if ( tmp < 0 ) tmp = 0;
 66             else if ( tmp > i ) tmp = i;
 67 
 68             tmpcal = cal( tmp, i - tmp );
 69             if ( dcmp( ans - tmpcal ) < 0 )
 70             {
 71                 ans = tmpcal;
 72                 ansX = tmp;
 73                 ansY = i - ansX;
 74             }
 75             else if ( dcmp( ans - tmpcal ) == 0 )
 76             {
 77                 if ( tmp < ansX )
 78                 {
 79                     ansX = tmp;
 80                     ansY = i - tmp;
 81                 }
 82                 else if ( tmp == ansX )
 83                 {
 84                     if ( ansY > i - tmp )
 85                     {
 86                         ansY = i - tmp;
 87                     }
 88                 }
 89             }
 90         }
 91 
 92         if ( dcmp(ans) <= 0 || ( ansX <= 0 && ansY <= 0 ) )
 93         {
 94             puts("0.00");
 95             puts("0 0");
 96             continue;
 97         }
 98 
 99         printf( "%.2f
", ans );
100         printf( "%d %d
", ansX, ansY );
101     }
102     return 0;
103 }