学步园

这一题wa了好久。。因为忽视了不同的machine会有相同的level的情况，所以记录那个level可用时不能简单地赋值。

排序过后，对machine的循环没必要每次从头开始。之前因为这个T了。

贪心，对于machine和task都是按x从大到小排序，x相同时按y从大到小排序。每次在x符合要求的machine中寻找level最小的一个。因为task是从大到小，后面的task肯定可以满足之前标记的x，然后再匹配到符合条件的最小level。

如果task1(use mach i)在task2前面，if task2可以使用mach i，但是money没有task1多，如果task2不可以使用task1，那么把task2匹配到别的机器更加make sense，不会减少完成的任务总数。

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<stdlib.h>
#include<vector>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include <ctype.h>
using namespace std;

//hdu 4864
int N;
int M;
pair<int,int> mach[100010];
pair<int,int> task[100010];
int num;
long long rev;
bool used[100010];
int rec[110];
int c[110];
void input()
{
   // cout<<N<<" "<<M<<endl;
    num=0;
    rev=0;
    for(int i=0;i<N;i++)
    {
        scanf("%d %d",&mach[i].first,&mach[i].second);
    }
    for(int i=0;i<M;i++)
    {
        scanf("%d %d",&task[i].first,&task[i].second);
    }

}
bool cmp(pair<int,int>a,pair<int,int>b)//sort machine and task
{
    if(a.first==b.first) return a.second>b.second;
    else return a.first>b.first;
}
void run()
{
    memset(used,true,sizeof(used));
    sort(mach,mach+N,cmp);
    sort(task,task+M,cmp);
    memset(rec,0,sizeof(rec));
    memset(c,0,sizeof(c));
   // int st=0;
    int j=0;
    for(int i=0;i<M;i++)
    {
        while(j<N&&mach[j].first>=task[i].first)
        {
           // if(used[j])
          //  {
                rec[mach[j].second]=j+1;//不可以这样直接赋值，因为不同的mach[i].second可能相同，会覆盖之前的有效值
                c[mach[j].second]++;
           // }
            j++;
        }


//        for(j=st;j<N;j++)   //这样第一次j就会循环到N，i之后都不会进入这个loop
//        {
//            if(used[j]&&mach[j].first>=task[i].first)
//            {
//                rec[mach[j].second]=j+1;
//            }
//        }
        for(int k=task[i].second;k<=100;k++)//之前写成for k=0 WA了。。
        {
            if(c[k])//rec[k]&&used[rec[k]-1]
            {
                num++;
                used[rec[k]-1]=false;
                c[k]--;
                rev+=500*task[i].first+2*task[i].second;
                break;
            }
        }
    }
}
int main()
{
   freopen("input.txt","r",stdin);
   while(scanf("%d %d",&N,&M)!=EOF)
   {
       input();
       run();
       printf("%d %I64d\n",num,rev);
   }
    return 0;
}