HDU - 4221

题目是英文题；一开始没看懂，后来结束后翻译，发现题目不难；

题意：

如果一项工作是完成后，他将得到一个惩罚比。
尽管他不可能在最后期限前完成每一项任务，但他希望所有任务的最大惩罚尽可能小。
他可以按任何顺序完成这些任务，一旦任务开始，就不能中断。
所有任务应在整数时间开始，时间从0开始。

如果一个工作在Di天之后，即Ti天完成，那么惩罚是Ti-Di

解题：
大概思路就是遍历每一个任务。 记录当前花费时间 ，以及当前任务i的惩罚。稍微处理一下。
题意是要记录最大的一次惩罚，而不是把所有惩罚相加…

贪心：
所有任务的最大惩罚尽可能小
策略：
将任务按结束时间从小到大排序，所求答案就是其中（Ti-Di）最大的那个。
假设时间t时刻，在未完成任务中取两个两个任务，
一个截止时间为d1,另一个为d2，
d1<d2,
若先选择d1，
max(cnt+c2-d2,cnt+c2+c1-d1)=cnt+c2+c1-d1;
若先选择d2，
max(cnt+c1-d1,cnt+c2+c1-d2)<cnt+c2+c1-d1;

#include<cstdio>
#include<iostream>
#include<iomanip>
#include<string.h>
#include<algorithm>
#define pi acos(-1.0)
#define MaxN 0x3f3f3f3f
#define MinN 0xc0c0c0c0
using namespace std;
typedef long long ll;
const int N=1e6+10;
struct node
{
   
    int x,y;
}s[N];
bool cmp(node a,node b)
{
   
    return a.y<b.y;
}
int main()
{
   
    int x,n,ans=1;
    ll cnt;
    cin>>x;
    while(x--)
    {
   
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d%d",&s[i].x,&s[i].y);
        sort(s,s+n,cmp);
        cnt=0;
        ll w=0;
        for(int i=0; i<n; i++)
        {
   
            w+=s[i].x;
            if(w-s[i].y>cnt)
                cnt=w-s[i].y;
        }
        printf("Case %d: %lld\n",ans++,cnt);
    }
    return 0;
}