Load Balancing 折半枚举大法好啊

　　　　　　　　　　　　　　　　　　　　　　　　　　　　Load Balancing

给出每个学生的学分。   将学生按学分分成四组，使得sigma (sumi-n/4)最小。         算法：   折半枚举

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <string>

 #include <vector>

 #include <set>

 #include <map>

 #include <stack>

 #include <queue>

 #include <sstream>

 #include <iomanip>

 using namespace std;

 typedef long long LL;

 const int INF=0x4fffffff;

 const int EXP=1e-;

 const int MS=;

 int num[MS];   //  学分为i的人数

 int sum[MS];     //   学分<=i的人数

 int main()

 {

       int T,kase=,n,x;

       scanf("%d",&T);

       while(T--)

       {

             memset(num,,sizeof(num));

             memset(sum,,sizeof(sum));

             scanf("%d",&n);

             for(int i=;i<n;i++)

             {

                   scanf("%d",&x);

                   num[x]++;

             }

             sum[]=num[];     //  note:  sum[0]!=0;

             for(int i=;i<MS;i++)

                   sum[i]=sum[i-]+num[i];

             //  折半枚举

             int ansa,ansb,ansc;

             int ta,tc;

             double sum1,sum2,sum3=INF;

             double ave=double(n)/4.0;

             for(int b=;b<MS-;b++)

             {

                   sum1=INF*1.0;

                   sum2=INF*1.0;

                   for(int a=;a<b;a++)

                   {

                         double t=fabs(double(sum[a])-ave)+fabs(double(sum[b]-sum[a])-ave);

                         if(t<sum1)

                         {

                               sum1=t;

                               ta=a;

                         }

                   }

                   for(int c=b+;c<MS-;c++)

                   {

                         double t=fabs(double(sum[c]-sum[b])-ave)+fabs(double(sum[MS-]-sum[c])-ave);

                         if(t<sum2)

                         {

                               sum2=t;

                               tc=c;

                         }

                   }

                   if(sum1+sum2<sum3)

                   {

                         sum3=sum1+sum2;

                         ansa=ta;

                         ansb=b;

                         ansc=tc;

                   }

             }

             printf("Case %d: %d %d %d\n",kase++,ansa,ansb,ansc);

       }

       return ;

 }