题面
贪心策略: 奶牛按照minSPF降序排序, 对于每只奶牛尽量选符合要求且SPF大的防晒霜, 若没有符合要求的防晒霜就去除这只牛.
证明: 由于每头参加晒太阳的牛都要涂防晒霜, 所以我们要多用防晒霜. 按minSPF降序排序后, 对于某一头牛用哪一瓶防晒霜的决策, 这头牛可以选SPF大的或SPF小的防晒霜, 由于minSPF递减, 所以大的小防晒霜的都不会因为SPF太小而以后不能使用, 但可能因为SPF太大而不能被后面的牛使用, 所以能用大的防晒霜的时候要先把大的用出去. 另外, 每头牛对答案的贡献都是1, 因此不存在某头牛用不了防晒霜需要抢前面的防晒霜的情况, 也不存在某头牛用得了却要留给后面的牛的情况.
这种考虑当前决策范围拓展到后面对整体影响的方法叫做范围缩放.
#include<cstdio>
#include<algorithm>
#define in inline
#define re register
#define int long long
using namespace std;
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
int n,m;
struct COW{
int mins,maxs;
bool operator<(const COW &t){return mins>t.mins;}
}cow[2600];
struct LO{
int s,c;
bool operator<(const LO &t){return s>t.s;}
}lo[2600];
signed main()
{
n=read(),m=read();
for(re int i=1;i<=n;++i) cow[i].mins=read(),cow[i].maxs=read();
for(re int i=1;i<=m;++i) lo[i].s=read(),lo[i].c=read();
sort(cow+1,cow+n+1);
sort(lo+1,lo+m+1);
int ans=0;
for(re int i=1;i<=n;++i)
{
for(re int j=1;j<=m;++j)
{
if(lo[j].s>=cow[i].mins&&lo[j].s<=cow[i].maxs&&lo[j].c>0)
{--lo[j].c,++ans;break;}
}
}
printf("%lld\n",ans);
return 0;
}
CGaZn的博客
最新评论