<2008年6月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

统计

  • 随笔 - 2
  • 文章 - 0
  • 评论 - 0
  • 引用 - 0

常用链接

留言簿(1)

随笔档案

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Computer
#include<iostream>
#include
<stdio.h>
#include
<stdlib.h>
using namespace std;
int n;                   //任务数目
struct node
{                      //用于表示任务的数据结构
   int start;             //任务的发布时间
   int len;              //任务的运行所需时间
}
;
node arr[
50100];
//调用qsort时提供的比较函数,使排序结果先按发布时间的增序,再按运行时间的增序
int sort(const  void* x, const void* y)

node
* a =(node*) x;
  node
* b=(node*) y;
 
if (a->start!=b->start) return a->start-b->start;
   
return a->len-b->len;
}


int heap[50100];          // 最小堆
int top;                 //堆中元素个数

//对堆进行向下调整,使之恢复堆结构
void filterdown(int start, int end)

int i=start, j=2*i+1int temp=heap[i];
while(j<=end)
{if(j<end&&heap[j]>heap[j+1]) j++;      //判断向左分支还是右分支进行调整
 if (temp<=heap[j]) break;
      
else{
       heap[i]
=heap[j]; i=j; j=2*j+1;        //交换父亲结点和儿子结点元素
         }

}

 heap [i]
=temp;
}

//取堆顶元素并将元素从堆中移除
int  outheap()
int i;
  i
=heap[0];           //取堆顶元素
  heap[0]=heap[top-1];  //取堆中最右元素作为新堆顶
  top--;
  filterdown(
0,top-1);   //对堆进行向下调整,使之恢复为堆结构
  return i;            //返回堆顶元素
}
                   //对堆进行向上调整,使之恢复为堆结构
void filterup (int start)

 
int  j=start, i=(j-1)/2int temp=heap[j];
   
while(j>0)
  
if(heap[i]<=temp) break;
    
else{heap[j]=heap[i]; j=i; i=(i-1)/2;}  //交换父亲结点和儿子结点元素
   }

 heap[j]
=temp;
}

 
//将新元素a插入堆中
void inrheap (int a)
{
heap[top]
=a;               // 将新元素插入堆数组右端叶子元素
    top++;                   //更新堆中元素数目
 filterup(top-1);            //从叶子向根进行调整
}

void process()
{
int i;
    _int64 time, sum;
for(i=0; i<n; i++)
{
cin
>>arr[i].start>>arr[i].len;       //读入数据
}

qsort(arr, n, 
sizeof(node), sort); 
time
=arr[0].start;
heap[
0]=arr[0].len;                   //将第1个任务插入堆中
top=1;
int index=1;
sum
=0;
//cout<<top<<endl;

while(1)
{  
    
while(top>0)
     
{
           i
=outheap();     //将堆顶任务出堆作为当前任务
           if(index>=n)   //没有尚待发布任务,则直接执行当前任务至结束
          {
            time
=time+i;         //更新当前时间
            sum=sum+time;      //累加总完成时间
            continue;
           }

          
if(time+i<=arr[index].start)
 
//尚待发布任务不影响当前任务,直接执行当前任务至结束
       
{
               time
=time+i;        //更新当前时间
               sum=sum+time;     //累加总完成时间
                continue;
              }

     i
=i-(arr[index].start-time); //将当前任务执行至新任务发布,剩余执行时间
     inrheap(i);             //看作一个新任务入堆
     i=index;
     time
=arr[index].start;
    
while(1)               //将当前时刻发布的所有新任务入堆
     {
        
if(arr[index].start!=arr[i].start) break;
        inrheap(arr[index].len);
        index
++;
        
if(index>=n) break;
     }

   }

  
if(index<n)              //将下一个新任务入堆
    {
     time
=arr[index].start;
     inrheap(arr[index].len);
     index
++;
    }
else
   
break;
  }

  printf(
"%I64d\n", sum);              //输出结果
}


int main()
{
freopen(
"computer.in""r", stdin);
 freopen(
"computer.out""w", stdout);
     
while(cin>>n)
      
{
         process();
      }

  
return 0;
}

posted on 2008-06-08 17:25 wcily123 阅读(205) 评论(0)  编辑 收藏 引用


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