舔狗

> “舔狗舔狗，
> 舔到最后，
> 一无所有。”

有 n 只舔狗，每只舔狗的心中都有自己朝思暮想的一位。

每个人虽然受到了一万次拒绝，还毅然第一万零一次鼓起勇气。

作为一个不食人间烟火的算法设计师，你早已看破红尘。但是，人世间的苦难仍让你挂念。看到众生在单恋中苦苦坚持，你决定普度众生，给大家找到一个最好的结局，让一无所有的舔狗尽量地少，让每个人都尽量能和自己喜欢的或喜欢自己的人修成正果。

也就是说，你需要给这 n 只舔狗配对，对于舔狗 i，他可以和他朝思暮想的人 $a_{i}$ 配对。另外，喜欢 i 的其他舔狗也可以和他配对。你需要让没有被配对的舔狗尽量少。

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; struct node{int x,p;}; bool operator < (node a,node b){return a.p>b.p;} priority_queue<node> q; int n,a[N],d[N],v[N]; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; d[a[i]]++; } for(int i=1;i<=n;i++) q.push({i,d[i]}); while(!q.empty()) { node k=q.top(); q.pop(); if(v[k.x]||v[a[k.x]]) continue; n-=2; v[k.x]=v[a[k.x]]=1; d[a[a[k.x]]]--; q.push({a[a[k.x]],d[a[a[k.x]]]}); } cout<<n<<endl; return 0; }

详情