题目大意:
有C头牛,L种防晒霜,每种防晒霜可以固定阳光对于某头涂了这种防晒霜的牛的强度。第i种防晒霜又有cover[i]个。每头牛有一个被晒得上限和下限,问有几头牛不会被晒伤并且强度大于下限
解题思路:
贪心
按照每头牛的被晒下限从大到小给牛排序 按照每一种防晒霜的作用从大到小给防晒霜排序 枚举每一头牛,枚举每一种防晒霜,用一次数量减一次。 也就是说防晒霜能用最大就用最大并且给下限最大的不会被晒伤的牛用,这就是最优解Accepted code:
#include#include using namespace std;struct cow{ int n,x;}a[2501];struct sun{ int s,c;}b[2501];int now,ans,c,l;bool cmp(cow x,cow y){ return x.n>y.n;}bool CMP(sun x,sun y){ return x.s>y.s;}int main(){ scanf("%d%d",&c,&l); for (int i=1;i<=c;i++) scanf("%d%d",&a[i].n,&a[i].x); for (int i=1;i<=l;i++) scanf("%d%d",&b[i].s,&b[i].c); sort(a+1,a+c+1,cmp); sort(b+1,b+l+1,CMP); for (int i=1;i<=c;i++) for (int j=1;j<=l;j++) { if (b[j].c&&b[j].s>=a[i].n&&b[j].s<=a[i].x) { ans++;b[j].c--;break; } } printf("%d",ans);}