首页 > 代码库 > hdu 4864 Task (贪心)

hdu 4864 Task (贪心)

# include <stdio.h>
# include <algorithm>
# include <string.h>
using namespace std;
struct node
{
	int t;
	int v;
	int yy;
};
struct node a[100010],b[100010];
bool cmp(node a1,node a2)
{
	if(a1.t==a2.t)//先按时间从大到小
		return a1.v>a2.v;//再按水平从大到小
	return a1.t>a2.t;
}
int main()
{
	int n,m,i,j;
	int map[100010];
	__int64 sum;
	while(~scanf("%d%d",&n,&m))
	{
		for(i=0;i<n;i++)
			scanf("%d%d",&a[i].t,&a[i].v);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&b[i].t,&b[i].v);
			b[i].yy=b[i].t*500+b[i].v*2;
		}
		sort(a,a+n,cmp);
		sort(b,b+m,cmp);
		int xx=0;
		memset(map,0,sizeof(map));
		sum=0;
		int cot=0;
		for(i=0;i<m;i++)
		{
             while(xx<n&&a[xx].t>=b[i].t)
				 map[a[xx++].v]++;//时间满足的标记
			 for(j=b[i].v;j<=100;j++)//从满足最小的价值开始搜
			 {
				 if(map[j])//存在这个价值
				 {
					 map[j]--;
					 sum+=b[i].yy;
					 cot++;
					 break;
				 }
			 }
		}
		printf("%d %I64d\n",cot,sum);
	}
	return 0;
}