今天做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);
}
}