【推理，贪心】UVa 1319

看到了大神的代码。理解了好久。。。真是差距。

题意：给出m, p, a, b，然后xi满足已下两个公式，求 x^p₁ + x^p₂ +...+ x^p_m的最大值。

1、-1/sqrt(a) <= xi <= sqrt(a); (a>0)

2、x1+x2+...+xm = b*sqrt(a);

注意：p为偶数。

解题思路：因为p为偶数，所以sqrt(a)和-1/sqrt(a)的p次方都为正数且sqrt(a) > 1/sqrt(a).所以贪心思想时尽量先取sqrt(a);当已经取的xi的和大于b*sqrt(a)时，再取(-1/sqrt(a))抵消多出的sqrt(a)。

为了简便计算同时减少sqrt()带来的误差。可以现将2式左右同乘以sqrt(a)。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 using namespace std;

 int main(){

     int m, p, a, b;

     while(~scanf("%d%d%d%d", &m, &p, &a, &b)) {

         int l = , r = ; //l, r分别代表-1/sqrt(a)与sqrt(a)的数目

         int sum = a * b;

         for(int i = ; i < m; i++) { //注意最后一个数不要考虑

             if(sum >= a) {

                 r++;

                 sum -= a; //xi已经取定sqrt(a)后,sum记得更新

             }

             else {

                 l++;

                 sum++;

             }

         }

         double ans = l / pow(sqrt(a), p) + r * pow (sqrt(a), p);

         ans += pow(sum/sqrt(a), p); //记得要除掉之前乘的sqrt(a);

         printf("%d\n", (int)(ans + 0.5));

     }

     return ;

 }

巴特西

【推理，贪心】UVa 1319 - Maximum

最新文章

热门文章