BZOJ1707：[Usaco2007 Nov]tanning分配防晒霜

我对贪心的理解：https://www.cnblogs.com/AKMer/p/9776293.html

题目传送门：https://www.lydsy.com/JudgeOnline/problem.php?id=1707

显然，如果一头奶牛能找到自己可以用的防晒霜就直接用，它用这一瓶防晒霜比它不用防晒霜留给别的牛用会更优，因为防晒霜与奶牛是一一对应的关系。那么问题就转化成了，如果一头奶牛有多瓶防晒霜可以用，用哪一瓶更好？

假设有两瓶防晒霜的\(spf\)值分别为\(x\)和\(y\)，且\(x<y\)。由于奶牛在无序的情况下我们并不能明显的区分出\(x\)与\(y\)孰轻孰重，所以我们先将奶牛按照\(maxspf\)为第一关键字，\(minspf\)为第二关键字从小到大排序。对于第\(i\)头奶牛都可以接受的\(x\)和\(y\)，对于\(i\)后面的奶牛只有这三种情况：

\(1\)、\(x\)和\(y\)都可用

\(2\)、\(x\)和\(y\)都不可用

\(3\)、\(x\)不可用，\(y\)可用

因为第\(3\)种情况，第\(i\)头奶牛使用\(spf\)值为\(x\)的防晒霜显然更优。所以每一头牛只需要找到在自己能接受范围内并且\(spf\)值最小的那一瓶防晒霜就可以了。

时间复杂度：\(O(nm)\)

空间复杂度：\(O(n)\)

代码如下：

#include <cstdio>

#include <algorithm>

using namespace std;

const int maxn=2505;

int n,m,ans;

int read() {

	int x=0,f=1;char ch=getchar();

	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;

	for(;ch>='0'&&ch<='9';ch=getchar())x=x*10+ch-'0';

	return x*f;

}

struct Cows {

	int min_spf,max_spf;

	bool operator<(const Cows &a)const {

		if(max_spf==a.max_spf)return min_spf<a.min_spf;

		return max_spf<a.max_spf;

	}

}c[maxn];

struct SPF {

	int v,sum;

	bool operator<(const SPF &a)const {

		return v<a.v;

	}

}s[maxn];

bool find(int l,int r) {

	for(int i=1;i<=m;i++)

		if(s[i].v>=l&&s[i].v<=r&&s[i].sum) {//防晒霜spf值在l到r内并且还有

			s[i].sum--;return 1;

		}

	return 0;

}

int main() {

	n=read(),m=read();

	for(int i=1;i<=n;i++) {

		c[i].min_spf=read();

		c[i].max_spf=read();

	}sort(c+1,c+n+1);//牛排序

	for(int i=1;i<=m;i++) {

		s[i].v=read();

		s[i].sum=read();

	}sort(s+1,s+m+1);//防晒霜排序

	for(int i=1;i<=n;i++)

		if(find(c[i].min_spf,c[i].max_spf))ans++;//如果有可以用的防晒霜就用

	printf("%d\n",ans);

	return 0;

}

巴特西

BZOJ1707：[Usaco2007 Nov]tanning分配防晒霜

\(1\)、\(x\)和\(y\)都可用

\(2\)、\(x\)和\(y\)都不可用

\(3\)、\(x\)不可用，\(y\)可用

最新文章

热门文章