leaving专题

codeforces 996 E. Leaving the Bar

题目:点击打开链接题意:给定一些向量,你可以改变它的符号,使得这些向量之和的长度小于1.5e6。分析:注意有方向,可以将速度分解成为x,y轴方向上的分量,每次贪心取最小,因为每次我贪心原则是一样的,最后的结果有可能大于1.5e6 ,我们需要加一些随机性,,多次贪心,直到结果满足题意。正解是每三个向量中都能找到两个向量合起来 <= 1e6,然后不断合并,最后只会剩下一个或者两个向量,如果一个向量肯定

【CodeForces 996E Leaving the Bar】【 贪心 】 【多次随机 random_shuffle】【选择向量的方向,使得最后向量的模小于范围】

【题意】 给你n个向量,你可以改变他们的符号,使得这些向量之和的长度小于1.5e6。 【思路】 容易想到贪心的大致思路:让尽量在选择的过程中让中间值的模长的绝对值尽可能小。但是也很容易想到反例。 博客中广泛采用 贪心+多次随机,一次贪心固定的选择可能选择不了好的结果,但是随机打乱数组的顺序,多次贪心使得得到结果   代码会好写,思想第一次遇到 【代码】 #include<bits/