算法:贪心
要使总盈利最大,那么尽可能使每一辆车获益最大,也就是每辆车在不超过自己所承载的货量的前提下选择收益最大的订单。
注意要把每辆车按承载货量从小到大排序,从承载货量小的货车开始选订单,因为它所选的订单,承载货量比它大的货车也能选,反之则不一定行。
举个简单例子:
样例:
2
5 20
8 10
2
9 6
如果9先选,则会选择第一个单子,获益20,然后8比6大,第二辆车就不能选了,所以总收益为20;但6先选,则获益20,然后9选择第二个单子,获益10,所以总收益为30。
这样就保证盈利最大化。
还需注意一下,排完序之后,货车的序号是会改变的,但题目输出的是货车原序号,所以弄个结构体存一下每辆货车的原序号。
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1010;
typedef pair<int,int> PIR;
struct cast
{
int x,w;
}a[N];
PIR b[N];
vector<PIR> C;
bool s[N];
bool com(const cast &a,const cast &b)
{
return a.x<b.x;
}
int main(void)
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
b[i]={x,y};
}
int k;
scanf("%d",&k);
for(int i=0;i<k;i++)
{
scanf("%d",&a[i].x);
a[i].w=i;
}
sort(a,a+k,com);
int ans=0,cot=0;
for(int i=0;i<k;i++)
{
int res=0;
for(int j=0;j<n;j++)
{
if(!s[j]&&a[i].x>=b[j].first)
{
res=max(res,b[j].second);
}
}
if(res!=0)
cot++;
for(int j=0;j<n;j++)
{
if(!s[j]&&a[i].x>=b[j].first)
{
if(b[j].second==res)
{
s[j]=true;
C.push_back({j,i});
break;
}
}
}
ans+=res;
}
printf("%d %d\n",cot,ans);
for(int i=0;i<C.size();i++)
{
printf("%d %d\n",C[i].first+1,a[C[i].second].w+1);
}
return 0;
}