考试时,想到了一个很类似的方法,但是总是差那么点,就是这么点,需要不断的努力啊!!!
题解:
基本思想是贪心。
对于价值c=500*xi+2*yi,yi最大影响100*2<500,所以就是求xi总和最大。可以先对机器和任务的时间从大到小排序。从最大时间的任务开始,找出满足任务时间要求的所有机器,从中找出等级最低且满足任务等级要求的机器匹配。依次对任务寻找满足要求的机器。
这几乎是把标程复制了一遍,因为其中的STL用的实在巧妙而且准确,自己写的话确实搞不出来。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long LL;
struct Task
{
int time;
int level;
};
Task task[],machine[];
bool cmp(Task a,Task b){
if(a.time==b.time) return(a.level>b.level);
else return(a.time>b.time);
}
int main()
{
int n,m;
while(scanf("%d%d", &n,&m)!=EOF)
{
for(int i=;i<n;i++)
scanf("%d%d",&machine[i].time,&machine[i].level);
for(int i=;i<m;i++)
scanf("%d%d",&task[i].time,&task[i].level);
sort(machine,machine+n,cmp);
sort(task,task+m,cmp);
int j=,count=;LL ans=;
map<int,int> le;
for(int i=;i<m;i++){
while(j<n&&task[i].time<=machine[j].time){
le[machine[j].level]++;
j++;
}
map<int,int>::iterator it=le.lower_bound(task[i].level);
if(it!=le.end()){
count++;
ans+=task[i].time*+task[i].level*;
int t=it->first;
le[t]--;
if(le[t]==) le.erase(t);
}
}
printf("%d %I64d\n",count,ans);
}
return ;
}
刚才发现大神博客题解上可以不用STL ,直接扫一遍就行了,自己还是太弱了。
转:http://blog.csdn.net/a601025382s/article/details/38046927
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; #define LL __int64
const int maxn=1e5+;
struct node{
int x,y;
}e[maxn],f[maxn];
int c[];
int cmp(node a,node b)
{
if(a.x==b.x)return a.y>b.y;
return a.x>b.x;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int i,j,k,num=;
LL ans=;
for(i=;i<n;i++)
scanf("%d%d",&e[i].x,&e[i].y);
for(i=;i<m;i++)
scanf("%d%d",&f[i].x,&f[i].y);
sort(e,e+n,cmp);
sort(f,f+m,cmp);
memset(c,,sizeof(c));
for(i=,j=;i<m;i++)
{
while(j<n&&e[j].x>=f[i].x)
{
c[e[j].y]++;
j++;
}
for(k=f[i].y;k<=;k++)
{
if(c[k])
{
num++;
c[k]--;
ans=ans+*f[i].x+*f[i].y;
break;
}
}
}
printf("%d %I64d\n",num,ans);
}
return ;
}