今天做http://202.120.80.191/problem.php?problemid=2588，开始把题目理解错了，原来每个进程的执行顺序是不可改变的。我没看到这一点。如果可以变，就成了多处理机多任务调度问题，看网上说这是NP问题。写了很久程序，才发现把题目理解错了。不过我觉得我的多处理机多任务调度的方法还是挺好的。
如果要把作业分成N份，先求出平均的处理时间（=总时间/N）。然后用动态规划求出小于等于该处理时间的一组作业。之后把剩余的作业堪称是分成N-1份，按照上面的方法做。直到求出N-1组小于等于平均处理时间的作业。则剩下的作业就是大于等于平均剩余时间的，求出其和就是结果。不知道效果怎么样，以后证明一下吧。
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn=110;
int m,n;
int time[maxn];
void dp(int avg)
{
int i;
int pre[maxn][2],a[maxn][2];
bool visit[maxn];
int b[maxn];
memset(visit,0,sizeof(visit));
a[0][0]=a[0][1]=0;
pre[0][0]=pre[0][1]=0;
for(i=1;i<=m;i++)
{
if(a[i-1][1]!=-1 && a[i-1][1]>a[i-1][0])
{
a[i][0]=a[i-1][1];
pre[i][0]=1;
}
else
{
a[i][0]=a[i-1][0];
pre[i][0]=0;
}
int t1=a[i-1][0]+time[i] ,t2=a[i-1][1]+time[i];
a[i][1]=-1;
if(t1<=avg)
{
a[i][1]=t1;
pre[i][1]=0;
}
if(a[i-1][1]!=-1 && t2<=avg && t2>t1)
{
a[i][1]=t2;
pre[i][1]=1;
}
}
int t;
if(a[m][0]>a[m][1]) t=0;
else t=1;
for(i=m;i>0;i--)
{
if(t==1) visit[i]=true;
t=pre[i][t];
}
int j;
for(i=1,j=0;i<=m;i++)
if(!visit[i])
b[++j]=time[i];
for(i=1;i<=j;i++)
time[i]=b[i];
m=j;
}
void solve()
{
int i,j;
int count,sum,avg;
for(i=1;i<n;i++)
{
count=sum=0;
for(j=1;j<=m;j++)
sum+=time[j];
avg=sum/(n-i+1);
dp(avg);
}
int res=0;
for(i=1;i<=m;i++)
res+=time[i];
printf("%d\n",res);
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
scanf("%d",&time[i]);
solve();
}
}
如果就本题而言，必须按顺序执行，只需二分即可。不是一般的简单
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int maxn=110;
int time[maxn];
int m,n;
bool check(int t)
{
int count=1,total=0;
for(int i=0;i<m;i++)
{
if(total+time[i]<=t)
total+=time[i];
else
{
total=time[i];
count++;
}
}
return (count<=n);
}
int main()
{
int t;
int low,up,mid;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
low=0,up=0;
for(int i=0;i<m;i++)
{
scanf("%d",&time[i]);
up+=time[i];
if(time[i]>low) low=time[i];
}
while(low<up)
{
mid=(low+up)/2;
if(check(mid))
up=mid;
else low=mid+1;
}
printf("%d\n",low);
}
}