题解 LA2911

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

\(1)\sum_{k=1}^m x_k = b\sqrt{a}\)

\(2)-\frac{1}{\sqrt{a}}\leq x_i\leq\sqrt{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\n", int(ans1 * pow(I, p) + ans2 * pow(-1 / I, p) + pow(goal / I, p) + 0.5));

	}

}

巴特西

题解 LA2911

最新文章

热门文章