C.进程调度实例讲解
2018-04-16 10:36:53         来源：zhagoodwell查的博客

C.进程调度

 Time Limit: 1000 MS Memory Limit: 65536 KB Total Submissions: 270 Accepted: 66

Description

Input

Output

Sample Input

4

11

33

22

44

Sample Output

3.5000

Hint

Source

2013 Anhui College Student Programming Contest--ahfywff

```# include <stdio.h>
# define M 1000
# define N 2
void Dsort(intint *tree[],int n);
int A[M][N],*P[M];
int main()
{
int n,i,time0=0,time1=0,sum;
//freopen("AAA.txt","r",stdin);
while(~scanf("%d",&n))
{
for(i=0;i<n;P[i]=A[i],i++)
scanf("%d %d",&A[i][0],&A[i][1]);
Dsort(P,n);
time1=P[0][0]+P[0][1];
time0=0;
sum=P[0][1];
//printf("%d %d %lld\n",time0,time1,sum);
for(i=1;i<n;i++)
{
if(P[i][0]<time1)time0=time1-P[i][0];
else
{
time0=0;//time0=当前进程-时间点=等待时间
time1=P[i][0];
}
time1+=P[i][1];//当前进程结束后的时间点
sum+=time0+P[i][1];
//printf("%d %d %lld\n",time0,time1,sum);
}
printf("%.4lf\n",sum*1.0/n);
}
return 0;
}
void Dsort(intint *tree[],int n)
{
int i,j=0,k,L,*R;
tree--;
while((i=++j)<=n)
{
R=tree[i];
while(i>1)
{
L=(i>>1);
for(k=0; k<N&&tree[L][k]==R[k]; k++);
if(tree[L][k]>=R[k]) break;
tree[i]=tree[L];
i=L;
}
tree[i]=R;
}
while(n)
{
R=tree[n];
tree[n--]=tree[1];
i=1;
L=2;
while(L<=n)
{
if(L<n)
{
for(k=0; k<N&&tree[L+1][k]==tree[L][k]; k++);
if(tree[L+1][k]>tree[L][k])L++;
}
for(k=0; k<N&&tree[L][k]==R[k]; k++);
if(tree[L][k]<=R[k]) break;
tree[i]=tree[L];
i=L;
L<<=1;
}
tree[i]=R;
}
tree++;
}  ```