2019河北省CCPC 舔狗【贪心】

河北省CCPC 舔狗【贪心】"/>

2019河北省CCPC 舔狗【贪心】

传送门

思路：每个舔狗只会喜欢一个人，每个人的选择就只有一个，要满足配对的舔狗数量最多，我们就应该选择喜欢人数少的舔狗来优先进行匹配。一个舔狗被多少人喜欢，就是这个点的入度。如果喜欢他的其中一个舔狗被配对了，那么这个舔狗的入度就应该减去1。我们就利用优先队列来维护每个舔狗的入度，然后去判断是否可以帮这只舔狗配对。

 

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<set>
#include<stack>
#include<map>
#include<new>
#include<vector>#define MT(a, b) memset(a,b,sizeof(a))
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai = acos(-1.0);
const double E = 2.718281828459;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5;int n,like[maxn],in[maxn];
int vis[maxn],ans;struct node{int e,d;bool friend operator<(node a,node b){return a.d>b.d;     ///优先选择入度少的舔狗}
};
void solve(){priority_queue<node>q;for(int i=1;i<=n;i++){q.push(node{i,in[i]});}while(!q.empty()){node w=q.top();q.pop();///如果已经被选择,或者他喜欢的人也配对了if(vis[w.e]||vis[like[w.e]])continue;   ans+=2;vis[w.e]=vis[like[w.e]]=1;///这两只舔狗配对///舔狗喜欢的人的入度减去1q.push(node{like[like[w.e]],--in[like[like[w.e]]]});}printf("%d\n",n-ans);   ///输入未配对的舔狗数
}
int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&like[i]);in[like[i]]++;}solve();return 0;
}