poj 2576 Tug of War

还是神奇的随机算法，，（看视频说这是爬山法？？）

其实就是把序列随机分成两半（我太弱，只知道random_shuffle），然后再每个序列里rand一个位置，x，y然后比较是不是交换之后是更优的。

然后重复这个过程。

神奇。。

 #include<cstdio>

 #include<cstring>

 #include<ctime>

 #include<iostream>

 #include<algorithm>

 #define LL long long

 using namespace std;

 int n,q[],a[],b[],ans1,ans2,ans;

 int main()

 {

     cin>>n;

     for (int i=; i<=n; i++) scanf("%d",&q[i]);

     int CNT=;

     while (CNT--)

     {

         random_shuffle(q+,q+n+);

         int lena=,lenb=,suma=,sumb=;

         for (int i=; i<=n/; i++) a[++lena]=q[i],suma+=q[i];

         for (int i=n/+; i<=n; i++) b[++lenb]=q[i],sumb+=q[i];

         int cnt=; ans=1e9;

         while (cnt--)

         {

             int x=rand()%lena+,y=rand()%lenb+;

             if (abs(suma-a[x]+b[y]-(sumb-b[y]+a[x]))<abs(suma-sumb))

                 suma=suma-a[x]+b[y],sumb=sumb-b[y]+a[x],swap(a[x],b[y]);

         }

         if (abs(suma-sumb)<ans) ans1=suma,ans2=sumb,ans=abs(suma-sumb);

     }

     if (ans1>ans2) swap(ans1,ans2);

     printf("%d %d\n",ans1,ans2);

 }