ZCMU 1018：突击战

Description

你有n个部下，每个部下需要完成一项任务。第i个部下需要你花Bi分钟交待任务，然后他会立刻独立地、无间断地执行Ji分钟后完成任务。你需要选择交代任务的顺序，使得所有任务尽早执行完毕（即最后一个执行完成的任务应尽早结束）。注意，不能同时给两个部下交待任务，但部下们可以同时执行他们各自的任务。

Input

输入包含多组数据，每组数据的第一行为部下的个数N（1<=N<=1000）；以下N行每行两个正整数B和J（1<=B<=10 000，1<=J<=10 000），即交待任务的时间和执行任务的时间。输入结束的标志为N=0。

Output

对于每组数据，先输出“Case #: ”（‘#’表示第几组数据），然后是所有任务完成的最短时间。

Sample Input

3

2 5

3 2

2 1

3

3 3

4 4

5 5

【分析】不能同时布置两个任务，但是可以同时执行多个任务，布置任务的时间的不可能节约的，所以尽量把执行任务时间长的先布置

#include<stdio.h>
int main()
{
    int n,index,temp,i,k,sum,j,caseN=0;

    while(~scanf("%d",&n))
    {
    caseN++;
    int a[n],b[n];
    if(n==0)break;
    for(i=0;i<n;i++)
        scanf("%d%d",&a[i],&b[i]);

    for(k=0;k<n-1;k++)//把布置任务时间长的放前面
    {
        index=k;
        for(i=k+1;i<n;i++)
            if(b[index]<b[i])
            index=i;
        temp=b[k];
        b[index]=b[k];
        b[k]=temp;
        
        temp=a[index];//执行时间b[]位置也要跟着a[]位置改变
        a[index]=a[k];
        a[k]=temp;
    }

    sum=a[0]+b[0];
    int j=b[0];//j表示距离前面任务全部完成还要所需时间
    for(i=0;i<n-1;i++)
    {
        if(a[i+1]+b[i+1]>=j)
        {
             sum+=a[i+1]+b[i+1]-j;//下一个任务布置加完成时间大于前面的，可以节约j小时
             j=b[(i+1)];
        }
        else j=j-a[(i+1)];//下一个任务布置加完成时间小于前面的，总时间不变，j缩短
    }
    printf("Case %d: %d\n",caseN,sum);

    }
return 0;
}
           

其他人更好的方法，比较总布置时间ans+执行完的时间(ex[i].j)VS之前任务完成总时间(sum),取较大值

https://blog.csdn.net/hzyhfxt/article/details/81414214

布置任务和执行任务换成结构体简单很多。