hdu4864不是一般的贪心

题目表达的非常清楚，也不绕弯刚开始以为最大权匹配，仔细一想不对，这题的数据双循环建图都会爆，只能先贪心试一下，但一想贪心也要双循环啊，怎么搞？

想了好久没头绪，后来经学长提醒，可以把没用到的先记录下来嘛，以后就不用从头去找了，就像cache一样。我想了想就忽然开窍了，对啊，任务的价值只是一到一百而已，把先前遍历到的没用到的机器先记录下来，以后碰到合适的就不用再从头搜到尾了啊！这样外层100000里层100应该是能过的！

那么就用一个数组来标记机器的价值，cache[i] 表示价值i的机器有多少个，用任务去找机器，也就是说外层循环是任务，每次先通过循环根据机器时间大于等于任务时间把符合的机器加到cache数组里，然后就要先明确一个贪心的原则，就是不浪费，也就是说第j个任务找机器的时候一定是找和它最近的机器是最符合的，你想啊，某台机器价值为8，某个任务价值为1，他们两匹配上了是不是很浪费？最不浪费的做法就是匹配相等价值的，但这太理想了，所以必须匹配价值最接近的！既然如此的话，就必须想排个序了，由大到小排，最后一个循环从任务的价值开始往上找合适的机器，找到了就把cache数组更新一下。这样这道题就ko了。

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

struct tam

{

    __int64 time,money;

}machine[],task[];

int cache[];

bool cmp(tam X,tam Y)

{

    if(X.time==Y.time) return X.money>Y.money;

    else return X.time>Y.time;

}

int main()

{

    int n,m;

            int c=;

        __int64 sum=;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        c=sum=;

        memset(cache,,sizeof(cache));

        for(int i=;i<n;i++)

            scanf("%I64d%I64d",&machine[i].time,&machine[i].money);

        sort(machine,machine+n,cmp);

        for(int j=;j<m;j++)

            scanf("%I64d%I64d",&task[j].time,&task[j].money);

        sort(task,task+m,cmp);

        int a,b;

        for(a=,b=; a<m;a++)

        {

            while(b<n&&machine[b].time>=task[a].time)

            {

                cache[machine[b].money]++;

                b++;

            }

            for(int k=task[a].money;k<=;k++)

            {

                if(cache[k])

                {

                    cache[k]--;

                    c++;

                    sum += (*task[a].time+*task[a].money);

                    break;

                }

            }

        }

        printf("%d %I64d\n",c,sum);

    }

}

巴特西

hdu4864不是一般的贪心

最新文章

热门文章