枪战Maf (思维好题 (starstar))
- 有 (n) 个人,用(1sim n) 进行编号,每个人手里有一把手枪。一开始所有人都选定一个人瞄准(有可能瞄准自己)。然后他们按某个顺序开枪,且任意时刻只有一个人开枪。因此,对于不同的开枪顺序,最后死的人也不同。
Input
- 输入(n)人数 (n<1000000)
- 接下来 (n) 个数,依次为每个人的 (aim)
Output
- 输出只有一行,共两个数,为要求最后死亡数目的最小和最大可能。
Sample Input
8
2 3 2 2 6 7 8 5
Sample Output
3 5
Hint
分析
-
设最大存活人数 (mx),最少存活人数 (mn)
-
如图,入度为 (0) 的点【绿框】必定存活,那么他所指的点【红圈】必定会死(早晚的事)。所以每有一个“绿框”,我们就:(text{mx++,mn++});
-
我们可以发现:
- 最小存活:如果 (2) 死之前射死了 (3) ((undie)标记),那么 (mn) 不变。
- 最大存活:如果 (2) 先死了,(3) 的入度减一,如果 (3) 的入度变为了 (0) ,进队(队列维护的是入度为 (0) 的点);
- 当然 (3) 也有可能入读不为 (0),那么它必定会构成环或链,想要尽量活的人多,那就要这个环或链隔一个人,打一个,最多就可以存活 (len/2) 个人。
- 如果环上有 (undie) 标记的点,我们可以设计,让该点最后死,然后再干掉他,这样环上就全部死掉。
-
最常见的还是构成环的情况【黄圈】(无 (undie) 标记),同理,
- 最小存活:(+1)(无论如何都会剩一个人)
- 最大存活:隔一个人打一个,可以最大存活 (len/2);
-
其实我们可以发现,拓扑序帮我们把一个大整体拆解成了一个个小问题。
Code
#include<stdio.h>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=1e6+5;
int n,Max,Min,q[maxn],aim[maxn],rd[maxn];
bool die[maxn],undie[maxn];
void Init(){
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&aim[i]);
rd[aim[i]]++;
}
for(int i=1;i<=n;++i)//入度为0的点必活
if(rd[i]==0){
Min++;//最小必活数+1
q[++Max]=i;//队列维护的是入度为0的点
}
}
void Solve(){
int head=1;
while(head<=Max){//扫描队列
int cur=q[head];head++;//取出队首并出队
if(die[aim[cur]]) continue;//队首目标已死(多个入度为0的点指向一个点)
die[aim[cur]]=1;//队首目标必死
int live=aim[aim[cur]];//队首目标的目标可死可不死,看决策
rd[live]--;//
undie[live]=1;//可以让他活,但想死的时候随时可以让他死,在环可以最后死
if(rd[live]==0)//虽然入度为0,但不一定是必活,所以Min不加
q[++Max]=live;
}
//下面处理只剩下环
for(int i=1;i<=n;++i)
if(rd[i] && !die[i]){
int len=0,flag=0;//len记录环大小,flag标记环上是否有undie的点
for(int j=i;!die[j];j=aim[j]){
len++;
flag|=undie[j];
die[j]=1;//标记已死,避免其他的再来计算
}
if(!flag && len>1) Min++;//len=1表示自环,必死
Max+=len/2;
}
printf("%d %d",n-Max,n-Min);
}
int main(){
Init();
Solve();
return 0;
}
原文链接: https://www.cnblogs.com/hbhszxyb/p/13212782.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/360862
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!