首页 > ACM题库 > HDU-杭电 > HDU 4221-Greedy?-贪心-[解题报告]HOJ
2015
05-23

HDU 4221-Greedy?-贪心-[解题报告]HOJ

Greedy?

问题描述 :

iSea is going to be CRAZY! Recently, he was assigned a lot of works to do, so many that you can’t imagine. Each task costs Ci time as least, and the worst news is, he must do this work no later than time Di!
OMG, how could it be conceivable! After simple estimation, he discovers a fact that if a work is finished after Di, says Ti, he will get a penalty Ti – Di. Though it may be impossible for him to finish every task before its deadline, he wants the maximum penalty of all the tasks to be as small as possible. He can finish those tasks at any order, and once a task begins, it can’t be interrupted. All tasks should begin at integral times, and time begins from 0.

输入:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then N lines following, each line contains two integers Ci and Di.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 100 000
3. 1 <= Ci, Di <= 1 000 000 000

输出:

The first line contains a single integer T, indicating the number of test cases.
Each test case includes an integer N. Then N lines following, each line contains two integers Ci and Di.

Technical Specification
1. 1 <= T <= 100
2. 1 <= N <= 100 000
3. 1 <= Ci, Di <= 1 000 000 000

样例输入:

2
2
3 4
2 2
4
3 6
2 7
4 5
3 9

样例输出:

Case 1: 1
Case 2: 3

题目链接:Click
here~~

题意:

给n个活动,每个活动需要一段时间C来完成,并且有一个截止时间D,当完成时间t大于截止时间完成时,会扣除t-D分,让你找出如何使自己所扣分的最大值最小。

解题思路:

贪心策略:每次先安排截止时间小的活动。

对于两个活动1、2,假设D1<D2,以起始时间为0为例。

如果先安排活动1,则扣分最大值为max(C1-D1,C1+C2-D2)。

如果先安排活动2,则扣分最大值为max(C2-D2,C1+C2-D1)。

显然第二个式子中的C1+C2-D1既大于C1-D1,又大于C1+C2-D2,则选择活动1是明智的。

#include <stdio.h>
#include <algorithm>
using namespace std;
struct TT
{
    int c,d;
    bool operator < (const TT& s)const
    {
        return d < s.d;
    }
}A[100002];
int main()
{
    int z,n;
    __int64 t,ans;
    scanf("%d",&z);
    for(int k=1;k<=z;k++)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            scanf("%d%d",&A[i].c,&A[i].d);
        sort(A,A+n);
        t = ans = 0;
        for(int i=0;i<n;i++)
        {
            t += A[i].c;
            if(ans < t - A[i].d)
                ans = t - A[i].d;
        }
        printf("Case %d: %I64d\n",k,ans);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/dgq8211/article/details/7538393