传送门
文章目录目录:
题意:思路:
目录: 题意:你有 n n n头奶牛, m m m中不同种类的麦片,每个麦片只有一箱,给你每个奶牛第一和第二喜欢的麦片,奶牛会先看第一喜欢的是否有,有的话直接拿走,否则看第二喜欢的是否有,有的话直接拿走,否则一箱不拿。
现在问题是奶牛排队领取,对于每个 0 ≤ i ≤ N − 1 0le ile N-1 0≤i≤N−1,求如果从队伍前面移除前 i i i头奶牛,有多少奶牛会取走一箱麦片。
1 ≤ n , m ≤ 1 e 5 1le n,mle 1e5 1≤n,m≤1e5
思路:第一反应是倒着考虑,考虑每加入一个奶牛会产生什么影响:
如果加入的奶牛第一喜好没有被之前的选择,那么直接选择即可。如果加入奶牛的第一喜好被之前选择了,那么由于其排在前面一定可以跟那个奶牛抢过来,所以递归处理前面的奶牛即可。
由于一个奶牛最多会被修改三次,复杂度得以保证 O ( n ) O(n) O(n)。
#include#define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define Mid (tr[u].l+tr[u].r>>1) #define pb push_back using namespace std; const int N=1000010,INF=0x3f3f3f3f,mod=1e9+7; typedef long long LL; int n,m; int id[N],cnt; int ans[N]; struct Node { int x,y; }a[N]; void dfs(int now) { if(now==-1) return; int x=a[now].x,y=a[now].y; if(id[x]==-1||id[x]>now) { dfs(id[x]); id[x]=now; } else if(id[y]==-1||id[y]>now) { dfs(id[y]); id[y]=now; } else cnt--; } void solve() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { int x,y; scanf("%d%d",&x,&y); a[i]={x,y}; } memset(id,-1,sizeof(id)); for(int i=n;i>=1;i--) { cnt++; int x=a[i].x; if(id[x]!=-1) dfs(i); else id[x]=i; ans[i]=cnt; } for(int i=1;i<=n;i++) printf("%dn",ans[i]); } int main() { int _=1; while(_--) { solve(); } return 0; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)