本文主要是介绍codeforces 996 E. Leaving the Bar，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：点击打开链接题意：给定一些向量，你可以改变它的符号，使得这些向量之和的长度小于1.5e6。
分析：注意有方向，可以将速度分解成为x，y轴方向上的分量，每次贪心取最小，因为每次我贪心原则是一样的，最后的结果有可能大于1.5e6 ，我们需要加一些随机性,，多次贪心，直到结果满足题意。正解是每三个向量中都能找到两个向量合起来 <= 1e6，然后不断合并，最后只会剩下一个或者两个向量，如果一个向量肯定 <= 1e6， 如果是两个向量一定 <= 1.5 * 1e6。
代码：
#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define MOD 1000000007
#define PI acos(-1.0)
const int N = 3e5+10;
const ll pp = 1500000;ll gcd(ll p,ll q)
{return q==0?p:gcd(q,p%q);
}
int to[4][2]= {{-1,0},{1,0},{0,-1},{0,1}};int n;struct nd
{ll x,y;int id;
} p[N];int a[N];ll d(ll a,ll b)
{return a*a+b*b;
}int main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n;for(int i=1; i<=n; i++){cin>>p[i].x>>p[i].y;p[i].id=i;}while(1){random_shuffle(p+1,p+n+1);ll x=0,y=0;for(int i=1; i<=n; i++){if(d(x-p[i].x,y-p[i].y)<d(x+p[i].x,y+p[i].y)){x-=p[i].x,y-=p[i].y;a[p[i].id]=-1;}else{x+=p[i].x,y+=p[i].y;a[p[i].id]=1;}}if(x*x+y*y<=pp*pp){for(int i=1; i<=n; i++){cout<<a[i];if(i!=n) cout<<" ";}break;}}return 0;
}这篇关于codeforces 996 E. Leaving the Bar的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
