程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu4864Task(貪心)

hdu4864Task(貪心)

編輯：C++入門知識

hdu4864Task(貪心)

題目鏈接：

啊哈哈，點我

題目：

Task

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2512 Accepted Submission(s): 643

Problem Description Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500*xi+2*yi) dollars.
The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.
The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.
Input The input contains several test cases.
The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).
The following N lines each contains two integers xi(0 The following M lines each contains two integers xi(0 Output For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.
Sample Input

Sample Output

1 50004

Author FZU
Source 2014 Multi-University Training Contest 1
Recommend We have carefully selected several similar problems for you: 4881 4880 4879 4878 4877

思路：

首先考慮獲得的報酬。。５００＊ｘｉ＋２＊ｙｉ，所以yi可以當做次要因素，主觀因素是時間。所以對任務，和機器的時間大- >小，等級大->小排序。。

接下來就是枚舉，將所有滿足機器運行時間》=任務時間的加入數組，然後選滿足完成任務的最小等級的機器去完成任務。這樣的巧妙之處在於後面的加進來的任務必定可以被先前加進來的機所完成。因為任務是按時間降序排列的。。那樣這道題就得到了完美的解決。。

代碼為：

#include
#include
#include
#include
using namespace std;

const int maxn=100000+10;
int level[100+10];
int n,m,sum;
__int64 ans;

struct P
{
    int xi,yi;
}machine[maxn],task[maxn];


bool cmp(P a,P b)
{
   if(a.xi==b.xi) return a.yi>b.yi;
   return a.xi>b.xi;
}

void read_data()
{
    for(int i=1;i<=n;i++)
        scanf("%d%d",&machine[i].xi,&machine[i].yi);
    for(int i=1;i<=m;i++)
        scanf("%d%d",&task[i].xi,&task[i].yi);
    sort(task+1,task+1+m,cmp);
    sort(machine+1,machine+1+n,cmp);
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        ans=sum=0;
        read_data();
        memset(level,0,sizeof(level));
        for(int i=1,j=1;i<=m;i++)
        {
            while(j<=n&&machine[j].xi>=task[i].xi)
            {
                level[machine[j].yi]++;
                j++;
            }
            for(int k=task[i].yi;k<=100;k++)
            {
                if(level[k])
                {
                    level[k]--;
                    ans=ans+500*task[i].xi+2*task[i].yi;
                    sum++;
                    break;
                }
            }
        }
        printf("%d %I64d\n",sum,ans);
    }
    return 0;
}