本文共 1050 字，大约阅读时间需要 3 分钟。
我们把1-400个时间点看成一个集合A，把所有的羊看成集合B，第i只羊喜欢区间[a[i],b[i]]，就给B中的i与A中的[a[i],b[i]]连一条边，这样就转化成了二分图匹配的模型了。我们每次询问只需在A中的[l,r]进行匹配。
本人采用匈牙利算法去做。#include#include #include #include #include using namespace std;typedef long long ll;const int maxn=4e2+5;bool map[maxn][maxn],vis[maxn]; //map[i][j]=1表示羊i对点j感兴趣，vis[i]=1/0表示点i是否访问过了int match[maxn],n,a[maxn],b[maxn]; //match[i]记录与点i匹配在一起的羊的编号，初始化为0bool find(int x,int l,int r){ for(int i=l;i<=r;++i) { if(map[x][i]&&!vis[i]) { vis[i]=1; if(!match[i]||find(match[i],l,r)) { match[i]=x; return 1; } } } return 0;}int main(){ int q; scanf("%d%d",&n,&q); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=1;i<=n;++i) scanf("%d",&b[i]); memset(map,0,sizeof(map)); for(int i=1;i<=n;++i) { for(int j=a[i];j<=b[i];++j) map[i][j]=1; } while(q--) { int l,r; scanf("%d%d",&l,&r); int ans=0; for(int i=l;i<=r;++i) match[i]=0; for(int i=1;i<=n;++i) { for(int j=l;j<=r;++j) vis[j]=0; if(find(i,l,r)) ++ans; } printf("%d\n",ans); } return 0;}
转载地址：http://gwdci.baihongyu.com/