Codeforces 996E Leaving the Bar (随机化)

题目连接：Leaving the Bar

题意：给你n个向量，你可以加这个向量或减这个向量，使得这些向量之和的长度小于1.5e6。

题解： 按照正常的贪心方法，最后的结果有可能大于1.5e6 。这里我们可以加一些随机性，多次贪心，直到结果满足题意。正解是每三个向量中都能找到两个向量合起来 <= 1e6，然后不断合并，最后只会剩下一个或者两个向量，如果一个向量肯定 <= 1e6， 如果是两个向量一定 <= 1.5 * 1e6。这是我第一遇到随机化的题~~~

 #include<bits/stdc++.h>

 using namespace std;

 #define fi first

 #define se second

 typedef long long LL;

 typedef pair<int,int> P;

 typedef pair<LL,LL> PL;

 const int MAX_N =1e5+;

 int N,M,T,S;

 struct node{

     int f,s,v;

 };

 node vec[MAX_N];

 int res[MAX_N];

 int main()

 {

     while(cin>>N){

         for(int i=;i<N;i++){

             scanf("%d%d",&vec[i].f,&vec[i].s);

             vec[i].v = i;

         }

         LL ti = ;

         while(){

             LL x = ;

             LL y = ;

             for(int i=;i<N;i++){

                 if((x + vec[i].f)*(x+vec[i].f) + (y+vec[i].s)*(y+vec[i].s) <=

                   (x - vec[i].f)*(x-vec[i].f) + (y-vec[i].s)*(y-vec[i].s)  ){

                     x += vec[i].f;

                     y += vec[i].s;

                     res[vec[i].v] = ;

                 }

                 else{

                     x -= vec[i].f;

                     y -= vec[i].s;

                     res[vec[i].v] = -;

                 }

             }

             if(x*x+y*y <= ti*ti){

                 for(int i=;i<N;i++){

                     printf("%d ",res[i]);

                 }

                 cout<<endl;

                 break;

             }

             random_shuffle(vec, vec+N);

         }

     }

     return ;

 }