computer.cpp

两道程序设计竞赛题目、代码（含注释）和测试用例

#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+1; int 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)/2; int 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;
}