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

本文主要是介绍【CodeForces 996E Leaving the Bar】【 贪心 】 【多次随机 random_shuffle】【选择向量的方向，使得最后向量的模小于范围】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题意】

给你n个向量，你可以改变他们的符号，使得这些向量之和的长度小于1.5e6。

【思路】

容易想到贪心的大致思路：让尽量在选择的过程中让中间值的模长的绝对值尽可能小。但是也很容易想到反例。

博客中广泛采用 贪心+多次随机，一次贪心固定的选择可能选择不了好的结果，但是随机打乱数组的顺序，多次贪心使得得到结果

 

代码会好写，思想第一次遇到

【代码】

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxn = 1e5 + 5;
const ll mod = 1e9 + 7;struct node {ll x, y, id;
}k[maxn];ll flag[maxn];int main() {ll n;while (~scanf("%lld", &n)) {for (ll i = 1; i <= n; i++) {scanf("%lld%lld", &k[i].x, &k[i].y);k[i].id = i;}while (1) {ll X = 0, Y = 0;for (ll i = 1; i <= n; i++) {if ((X+k[i].x)*(X+k[i].x) + (Y+k[i].y)*(Y+k[i].y) < (X-k[i].x)*(X-k[i].x) + (Y-k[i].y)*(Y-k[i].y)) {flag[k[i].id] = 1;X += k[i].x;Y += k[i].y;}else {flag[k[i].id] = -1;X -= k[i].x;Y -= k[i].y;}}if (X*X + Y * Y <= 1.5e6*1.5e6) {break;}random_shuffle(k + 1, k + 1 + n);}for (ll i = 1; i <= n; i++) {if (i != 1)printf(" ");printf("%d", flag[i]);}}
}

 

这篇关于【CodeForces 996E Leaving the Bar】【 贪心 】 【多次随机 random_shuffle】【选择向量的方向，使得最后向量的模小于范围】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---