1124: [POI2008]枪战Maf

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 617 Solved: 236
[Submit][Status][Discuss]

Description

有n个人，每个人手里有一把手枪。一开始所有人都选定一个人瞄准（有可能瞄准自己）。然后他们按某个顺序开枪，且任意时刻只有一个人开枪。因此，对于不同的开枪顺序，最后死的人也不同。

Input

输入n人数<1000000 每个人的aim

Output

你要求最后死亡数目的最小和最大可能

Sample Input

8
2 3 2 2 6 7 8 5

Sample Output

3 5

HINT

Source

[Submit][Status][Discuss]

分析

很有意思的一道贪心题目，主要是代码实现上的细节挺多，要不就是今晚太困了……

两个问题要分开分析，有不同的贪心思路。

首先，枪杀关系类似于有向图。按照联通块进行划分，其可以分为大致三种情况——

单独一个点形成的自环。显然这个点必定会死，不论是最多死亡人数还是最少死亡人数，都会使答案+1。
一条链，最后的一个点可能是个自环，类似于1->2->3->4->5->5。显然这条链上除了1，其他点通过合理的顺序都可以被枪杀，所以最多死亡人数是len-1。因为1不会死，我们贪心的让1先杀死2，这样3就可以活下来；因为3可以活下来，所以贪心的杀死4，这样5就可以活下来。依次类推，得到一个贪心思路——如果当前认为一个点可以活，则贪心的杀死他的枪杀目标，给他枪杀目标的目标以更大的生存机会。如果这样发现，其枪杀目标的目标已经没有入边，则认为其也是可以活下来的，继续这一过程。
最为复杂的是基环内向树和简单的有向环。如果是环，那么至少要有一个点活着，最多只能有(size/2)个点活着。而如果是基环树，至少每条链的尾端要活着，至多可以做到类似于上面的贪心。

代码

 #include <bits/stdc++.h>

 using namespace std;

 #define N 1000100

 int n, to[N], ans1, ans2;

 namespace query1

 {

     int cnt[N];

     int vis[N];

     int que[N];

     void solve(void)

     {

         ans1 = n;

         memset(cnt, , sizeof(cnt));

         memset(vis, , sizeof(vis));

         for (int i = ; i <= n; ++i)

             ++cnt[to[i]];

         for (int i = ; i <= n; ++i)

             if (i == to[i])

                 --cnt[i], vis[i] = ;

         int head = , tail = ;

         for (int i = ; i <= n; ++i)

             if (!vis[i] && !cnt[i])

                 que[tail++] = i;

         while (head != tail)

         {

             int top = que[head++];

             vis[top] = ; --ans1;

             if (!vis[to[top]])

             {

                 vis[to[top]] = ;

                 if (!vis[to[to[top]]] && --cnt[to[to[top]]] == )

                     que[tail++] = to[to[top]];

             }

         }

         for (int i = ; i <= n; ++i)

             if (!vis[i])

             {

                 int siz = ;

                 for (int j = i; !vis[j]; j = to[j])

                     vis[j] = , ++siz;

                 ans1 -= (siz >> );

             }

     }

 }

 namespace query2

 {

     int cnt[N];

     int vis[N];

     int que[N];

     int flg[N];

     void solve(void)

     {

         ans2 = n;

         memset(cnt, , sizeof(cnt));

         memset(vis, , sizeof(vis));

         memset(flg, , sizeof(flg));

         for (int i = ; i <= n; ++i)

             ++cnt[to[i]];

         for (int i = ; i <= n; ++i)

             if (i == to[i])

                 --cnt[i], vis[i] = ;

         int head = , tail = ;

         for (int i = ; i <= n; ++i)

             if (!vis[i] && !cnt[i])

                 que[tail++] = i, --ans2;

         while (head != tail)

         {

             int top = que[head++];

             flg[to[top]] = vis[top] = ;

             if (--cnt[to[top]] == )

                 que[tail++] = to[top];

         }

         for (int i = ; i <= n; ++i)

             if (!vis[i])

             {

                 int flag = ;

                 for (int j = i; !vis[j]; j = to[j])

                     vis[j] = , flag |= flg[j];

                 if (!flag)--ans2;

             }

     }

 }

 signed main(void)

 {

     scanf("%d", &n);

     for (int i = ; i <= n; ++i)

         scanf("%d", to + i);

     query1::solve();

     query2::solve();

     printf("%d %d\n", ans1, ans2);

 }

BZOJ_1124.cpp

@Author: YouSiki

枪战Maf

BZOJ 1124: [POI2008]枪战Maf