UVAlive 2911 Maximum(貪心)

Let x1, x2,..., xm be real numbers satisfying the following conditions:

a)
-xi ;
b)
x1 + x2 +...+ xm = b *  for some integers a and b (a > 0).
Determine the maximum value of xp1 + xp2 +...+ xpm for some even positive integer p.

Input
Each input line contains four integers: m, p, a, b ( m2000, p12, p is even). Input is correct, i.e. for each input numbers there exists x1, x2,..., xm satisfying the given conditions.

Output
For each input line print one number - the maximum value of expression, given above. The answer must be rounded to the nearest integer.

#include <stdio.h>  
#include <math.h>  
 
double m, p, a, b, numa, anum, sb, sum; 
int main() { 
    while (~scanf("%lf%lf%lf%lf", &m, &p, &a, &b)) { 
        sum = 0; 
        sb = a * b; 
        numa = anum = 0; 
        for (int i = 0; i < m - 1; i ++) {//注意只進行m - 1次操作，最後一部分要單獨考慮  
            if (sb < a) { 
                anum ++; 
                sb ++; 
            } 
            else { 
                sb -= a; 
                numa ++; 
            } 
        } 
        sum += anum / pow(sqrt(a), p); 
        sum += numa * pow(sqrt(a), p); 
        sum += pow((sb / sqrt(a)), p);//剩下的部分  
        printf("%d\n", int(sum + 0.5)); 
    } 
    return 0; 
} 

#include <stdio.h>
#include <math.h>

double m, p, a, b, numa, anum, sb, sum;
int main() {
 while (~scanf("%lf%lf%lf%lf", &m, &p, &a, &b)) {
  sum = 0;
  sb = a * b;
  numa = anum = 0;
  for (int i = 0; i < m - 1; i ++) {//注意只進行m - 1次操作，最後一部分要單獨考慮
   if (sb < a) {
    anum ++;
    sb ++;
   }
   else {
    sb -= a;
    numa ++;
   }
  }
  sum += anum / pow(sqrt(a), p);
  sum += numa * pow(sqrt(a), p);
  sum += pow((sb / sqrt(a)), p);//剩下的部分
  printf("%d\n", int(sum + 0.5));
 }
 return 0;
}

 

Sample Input

1997 12 3 -318
10 2 4 -1

Sample Output

189548
6題意：給定m,p,a,b.根據題目中的兩個條件.求出 xp1 + xp2 +...+ xpm 最大值..

思路:貪心.由於題目明確了p是負數,所以x^p，x絕對值越大的時候值越大。。然後我們根據條件。發現x盡可能取sqrt(a)是最好的。但是不一定能全部取得sqrt(a)。那麼多出來的還要拿一部分去抵消。這時候我們就用-1/sqrt(a)去抵消是最好的。這樣就能滿足最大了。不過要注意。抵消到最後剩下那部分也要考慮進去。

代碼：