UVa1467 Installations

In the morning, service engineers in a telecom company receive a list of jobs which they must serve today. They install telephones, internet, ipTVs, etc and repair troubles with established facilities. A client requires a deadline when the requested job must be completed. But the engineers may not complete some jobs within their deadlines because of job overload. For each job, we consider, as a penalty of the engineer, the difference between the deadline and the completion time. It measures how long the job proceeds after its deadline. The problem is to find a schedule minimizing the sum of the penalties of the jobs with the two largest penalties.

A service engineer gets a list of jobs J_i with a serving time s_i and a deadline d_i. A job J_i needs time s_i, and if it is completed at time C_i, then the penalty of J_i is defined to be max{0, C_i - d_i}. For convenience, we assume that the time t when a job can be served is 0 $\le$ t < $\infty$ and s_i and d_i are given positive integers such that 0 < s_i $\le$ d_i. The goal is to find a schedule of jobs minimizing the sum of the penalties of the jobs with the two largest penalties.

For example, there are six jobs J_i with the pair (s_i, d_i) of the serving time s_i and the deadline d_i, i = 1,..., 6, where (s₁, d₁) = (1, 7), (s₂, d₂) = (4, 7), (s₃, d₃) = (2, 4), (s₄, d₄) = (2, 15), (s₅, d₅) = (3, 5), (s₆, d₆) = (3, 8). Then Figure 1 represents a schedule which minimizes the sum of the penalties of the jobs with the two largest penalties. The sum of the two largest penalties of an optimal schedule is that of the penalties of J₂ and J₆, namely 6 and 1, respectively, which is equal to 7 in this example.

$\epsfbox{p4850.eps}$

Figure 1. The optimal schedule of the example

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases Tis given on the first line of the input. The first line of each test case contains an integer n ( 1 $\le$ n $\le$ 500), the number of the given jobs. In the next n lines of each test case, the i-th line contains two integer numbers s_i and d_i, representing the serving time and the deadline of the job J_i, respectively, where1 $\le$ s_i $\le$ d_i $\le$ 10, 000.

Output

Your program is to write to standard output. Print exactly one line for each test case. The line contains the sum of the penalties of the jobs with the two largest penalties.

The following shows sample input and ouput for three test cases.

Sample Input

Sample Output

7
0
14
题目大意：工程师要安装N个服务，每个服务需要si安装时间，并且有一个截止时间di。对于每个服务，如果超过期限都会有一个惩罚值，假设ci为实际完成时间，那么惩罚值为max(0,ci-di)。题目要求让惩罚值最大的两个任务的惩罚值之和最小。
题解:刚开始YY了一个解法，那就是用选择排序的方式来安排N个服务的顺序，对于服务i和j，max(0,a[i].s-a[i].d)+max(0,a[i].s+a[j].s-a[j].d)与max(0,a[j].s-a[j].d)+max(0,a[j].s+a[i].s-a[i].d)比较，如果前者值大于后者值，那么两个服务交换一下位置。但是这样答案不是最优的，它只能不超过期限的服务往前排。。。因此此方法不行。我们采取另外一种策略：先对N个服务排序，截止时间短的排前面，如果截止时间相同，则让安装时间短的排前面，这样总不至于得到更糟的结果。排好序之后求出两个惩罚值最大的两个任务的惩罚值的和，并一个变量d记录两个任务中靠后的位置。然后就是让在0~d-1的位置的一个服务p放置到位置d上，并p+1~d区间的服务的位置向前挪一位。然后计算一下惩罚值最大的两个任务的惩罚值之和，求出其中最小的即是最终答案。

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 #define MAXN 505
  4 typedef struct
  5 {
  6     int s,d;
  7 } NODE;
  8 NODE a[MAXN];
  9 int n;
 10 int max(int a,int b)
 11 {
 12     return a>b?a:b;
 13 }
 14 int min(int a,int b)
 15 {
 16     return a<b?a:b;
 17 }
 18 void qsort(int l,long r)
 19 {
 20     int i,j;
 21     NODE mid,temp;
 22     i=l ;
 23     j=r;
 24     mid=a[(l+r)>>1];
 25     while(i<=j)
 26     {
 27         while((a[i].d<mid.d)||((a[i].d==mid.d)&&(a[i].s<mid.s))) i++;
 28         while((a[j].d>mid.d)||((a[j].d==mid.d)&&(a[j].s>mid.s))) j--;
 29         if(i<=j)
 30         {
 31             temp=a[i];
 32             a[i]=a[j];
 33             a[j]=temp;
 34             i++;
 35             j--;
 36         }
 37     }
 38     if(i<r) qsort(i,r);
 39     if(j>l) qsort(l,j);
 40 }
 41 int main(void)
 42 {
 43     int i,j,T;
 44     int ans,max1,max2,t,d,maxs;
 45     scanf("%d",&T);
 46     while(T--)
 47     {
 48         scanf("%d",&n);
 49         for(i=0; i<n; i++)
 50             scanf("%d%d",&a[i].s,&a[i].d);
 51         qsort(0,n-1);
 52         ans=0;
 53         max1=0;
 54         max2=0;
 55         for(i=0; i<n; i++)
 56         {
 57             ans+=a[i].s;
 58             t=max(ans-a[i].d,0);
 59             if(t>max1)
 60             {
 61                 max2=max1;
 62                 max1=t;
 63                 d=i;
 64             }
 65             else if(t>max2)
 66             {
 67                 max2=t;
 68                 d=i;
 69             }
 70         }
 71         maxs=max1+max2;
 72         for(i=0; i<d; i++)
 73         {
 74             ans=0;
 75             max1=0;
 76             max2=0;
 77             for(j=0; j<=d; j++)
 78             {
 79                 if(i==j) continue;
 80                 ans+=a[j].s;
 81                 t=max(ans-a[j].d,0);
 82                 if(t>max1)
 83                 {
 84                     max2=max1;
 85                     max1=t;
 86                 }
 87                 else if(t>max2)
 88                     max2=t;
 89             }
 90             ans+=a[i].s;
 91             t=max(ans-a[i].d,0);
 92             if(t>max1)
 93             {
 94                 max2=max1;
 95                 max1=t;
 96             }
 97             else if(t>max2)
 98                 max2=t;
 99         maxs=min(maxs,max1+max2);
100         }
101         printf("%d\n",maxs);
102     }
103 return 0;
104 }