HDU 4864貪欲
1661 ワード
//無言で、試合の時に三人で大まかなことを考えたが、結局三人とも考えが未熟だったので、正解に近いのにできなかった
//考え方:欲張り.明らかにxiが利益に与える影響はもっと大きく、c[i]で時間と等級を巧みに結びつけた.
//考え方:欲張り.明らかにxiが利益に与える影響はもっと大きく、c[i]で時間と等級を巧みに結びつけた.
#include <iostream>
#include<stdio.h>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define N 100009
using namespace std;
int n,m;
int c[105];
struct node
{
int x,y;
}e[N],f[N];
int cmp(node a,node b)
{
if(a.x==b.x) return a.y>b.y;
return a.x>b.x;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
int Max=0;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&e[i].x,&e[i].y);
Max=max(Max,e[i].y);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&f[i].x,&f[i].y);
}
sort(e+1,e+1+n,cmp);
sort(f+1,f+1+m,cmp);
memset(c,0,sizeof(c));
int num=0;
__int64 sum=0;
int j=1;
for(int i=1;i<=m;i++)//
{
while(j<=n&&e[j].x>=f[i].x)// ，
{
c[e[j].y]++;
j++;
}
for(int k=f[i].y;k<=Max;k++)// c[k] 0
{
if(c[k])
{
num++;
c[k]--;
sum+=500*f[i].x+2*f[i].y;
break;
}
}
}
printf("%d %I64d
",num,sum);
}
return 0;
}