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 ;
}
05-06 23:28