为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 319342
  • 排名 - 75

最新评论

阅读排行榜

评论排行榜

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


posted on 2009-10-06 15:08 baby-fly 阅读(683) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理