首页 > 代码库 > 潍坊一中模拟赛10.2 妖精大作战
潍坊一中模拟赛10.2 妖精大作战
【Description】
潍坊一中有绿化很好，产生了很多树精草精动物精等妖精，妖王经常安排妖精们打架来消磨时间，其中有N 个妖精开始了一场约架 ，现在每一只妖精都已经把自己所有的弹幕瞄准了一只妖精(有可能是自己)。
这些妖精的能力值都非常高，所以一旦将弹幕发射出去，瞄准的妖精必死无疑。
为了使问题变得更有趣一些，妖王打算让这些妖精按照某个顺序来发射弹幕。一旦某个妖精已经被打死了，那么他将退出战斗。
可以预见到，按照不同的顺序，最后死亡的妖精数量是不一样的。
妖王想知道，死亡的妖精数量的最大值和最小值、分别是多少 ，但是妖王的智商不高，所以安排潍坊一中信息学奥赛小队的同学来帮助他，如果不能帮他解决问题，那妖精们下一次的攻击对象就是你！！
【Input】
第一行一个整数N
接下来N 行每行一个整数，第i 行的数值表示第i 只妖精瞄准的妖精是谁 ，保证这个整数在 [1, n]范围内。
【Output】
一行两个整数，死亡的妖精数量的最大值和最小值。
【Sample Input】
4
2 3 1 1
【Sample Output】
3 2
【Hint】
最大：按照2-1-4 的顺序发射弹幕。
最小：4-2
分析：
最大杀死数： 链上的只有入度为0是杀不死的，不与链相连的环上的有一个杀不死的。
最小杀死数 入度为0的是杀不死的，要获得最小值，链上的先从入度为0的开始攻击，切断其他的被攻击点。
环上的有（len+1)/2的是杀死的。
#include <cstdio>#include <cstdlib>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int MAXN = 1500001;int p[MAXN], n, into[MAXN];//into 出度 bool vis[MAXN], aj[MAXN], die[MAXN];struct Tqueue{//自定义队列 int l, r, data[MAXN]; void clear() { l = 1; r = 0; } bool empty() { return l > r; } void push(int t) { data[++r] = t; } int pop() { return data[l++]; }} Q;int getmin()//最少杀死数，从出度为0开始杀别的妖精 { int ans = 0; memset(vis, 0, sizeof(vis)); memset(into, 0, sizeof(into)); Q.clear(); for (int i = 1; i <= n; i++) ++into[p[i]];//计算出度 for (int i = 1; i <= n; i++) if (into[i] == 0) Q.push(i), vis[i] = true;//出度为0进队列 while(!Q.empty()){ int x = Q.pop();//队首元素 if (die[x]) continue; x = p[x];//找到队首的攻击对象 if (die[x]) continue; ++ans;//如果没死，die了他 die[x] =true; vis[x] =true; //处理后事 --into[p[x]]; //他的攻击对象安全一点 if (into[p[x]] == 0) Q.push(p[x]), vis[p[x]] = true;//如果已经安全，进队列。 } for (int i = 1; i <= n; i++) if (!vis[i]){//处理环 int t = p[i], len = 1; vis[p[i]] = true; while(t != i) { ++len; t = p[t]; vis[t] = true; } ans += 1 + ((len - 1) >> 1);//最少的杀死数是一半 } return ans;}int getmax()//求最多杀死数 { int ans = n; memset(into, 0, sizeof(into)); memset(vis, 0, sizeof(vis)); memset(aj, 0, sizeof(aj)); Q.clear(); for (int i = 1; i <= n; i++) ++into[p[i]];//入度为0，杀不死，减去 for (int i = 1; i <= n; i++) if (into[i] == 0) { --ans; Q.push(i); vis[i] = true; } while(!Q.empty()){ int x = Q.pop(); --into[p[x]]; aj[p[x]] = true; if (into[p[x]] == 0) { Q.push(p[x]); vis[p[x]] = true; } } for (int i = 1; i <= n; i++) if (!vis[i]){ int t = p[i]; bool jc = !aj[i]; vis[i] = true; while(t != i) { vis[t] = true; jc &= !aj[t]; t = p[t]; }//处理环， if (jc && (!(i == p[i]))) --ans;//一个环中只有一个活着的，减去。 } return ans;}int main(){ freopen("kill.in", "r", stdin); freopen("kill.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &p[i]); printf("%d %d\n", getmin(), getmax());}
潍坊一中模拟赛10.2 妖精大作战
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。