题解 LA2911

题目大意 多组数据，每组数据给定整数 (m,p,a,b)，满足 (a>0)，(2leq pleq12) 且 (p) 为偶数。要求求出一列数 (x_1,x_2,cdots,x_m)，满足:

(1)sum_{k=1}^m x_k = bsqrt{a})

(2)-frac{1}{sqrt{a}}leq x_ileqsqrt{a})

并且输出 (sum_{k=1}^m x_k^p) 的最大值。

分析 既然给定 (p) 是偶数，则 (x^p) 最大等价于 (|x|) 最大。那么我们可以贪心，使 (-frac{1}{sqrt{a}}) 和 (sqrt{a}) 占据 (m-1) 个，剩下那个单独考虑。但这样容易精度不够，所以把 (sqrt{a}) 当做 (a) 来做。

#include<bits/stdc++.h>
using namespace std;

int m, p, a, b;
int ans1, ans2;

int main()
{
	while(~scanf("%d%d%d%d", &m, &p, &a, &b)) {
		ans1 = ans2 = 0;
		
		int goal = b * a;
		double I = sqrt(a);
		
		while(--m) {
			if(goal >= a) goal -= a, ++ans1;
			else ++goal, ++ans2;
		}
		
		printf("%d
", int(ans1 * pow(I, p) + ans2 * pow(-1 / I, p) + pow(goal / I, p) + 0.5));
	}
}