首页技术正文

CF111A Petya and Inequiations 题解

程序员淑萍技术 2022年11月18日

0 收藏 960 点赞 2,852 浏览 745 个字

Content

请找出一个由 $n$ 个正整数组成的数列 $\{a_1,a_2,\dots,a_n\}$，满足以下两种条件：

$\sum\limits_{i=1}^na_i^2\geqslant x$。
$\sum\limits_{i=1}^na_i\leqslant y$。

数据范围：$1\leqslant n\leqslant 10^5$，$1\leqslant x\leqslant 10^{12}$，$1\leqslant y\leqslant 10^6$。

Solution

我们不妨设 $f(x)=x^2(x>0)$，然后画出这个函数的图像之后不难看出 $f(x)$ 是增函数，且随着 $x$ 的增长，其值越来越大。因此我们考虑这样的一个贪心：将前 $n-1$ 个数全部赋值为 $1$，最后一个数赋值为 $y-(n-1)=y-n+1$。然后再计算 $1^2\cdot(n-1)+(y-n+1)^2$ 是否 $\geqslant x$，是的话直接输出方案，否则输出 $-1$。

另外这题还要注意一个特判：因为题目中并没有保证 $y\geqslant n$，而要求的数列又要求全是正整数。所以如果 $y<n$，那么也无法得到合法的方案，输出 $-1$。

Code

ll ans[100007], xx;int main() {
int n = Rint; ll x = Rll; int y = Rint;
if(y < n) return puts("-1"), 0;
F(i, 2, n) ans[i] = 1;
ans[1] = y - n + 1;
F(i, 1, n) xx += 1ll * ans[i] * ans[i];
if(xx < x) return puts("-1"), 0;
F(i, 1, n) write(ans[i]), puts("");
return 0;
}