[BZOJ 1124][POI 2008] 枪战 Maf

Description#

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

Input#

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

Output#

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

Sample Input#

8
2 3 2 2 6 7 8 5

Sample Output#

3 5

我也不会啊#

树DPTH_Hugh
liu_runda

贴代码

1
#include <cstdio>
2
#include <cstring>
3
#include <queue>
4
using namespace std;
5
int a[1000005], Maxn, t, Min, Max;
6
int times[1000005];
7
bool die[1000005], nodie[1000005];
8
int Q[1000005];
9
int main()
10
{
11
    //freopen("maf.in", "r", stdin);
12
    //freopen("maf.out", "w", stdout);
13
    int n;
14
    scanf("%d", &n);
15
    for (int i = 1; i <= n; i++)
16
    {
17
        scanf("%d", &a[i]);
18
        times[a[i]]++;
19
    }
20
    //Q.resize(1000001);
21
    for (int i = 1; i <= n; i++)
22
    {
23
        if (!times[i])
24
        {
25
            Max++;
26
            Q[++Min] = i;
27
        }
28
    }
29
    //printf("%d\n",Max);
30

31
    //for (vector<int>::iterator it = Q.begin(); it != Q.end(); it++)
32
    for (int i = 1; i <= Min; i++)
33
    {
34
        //printf("%d---------%d=======\n",it-Q.begin(),*it);
35
        int k = a[Q[i]];
36
        if (die[k])
37
            continue;
38
        die[k] = 1;
39
        nodie[a[k]] = 1;
40
        --times[a[k]];
41
        if (!times[a[k]])
42
        {
43
            Q[++Min]=a[k];
44
        }
45
    }
46
    int sum;
47
    bool All_NoDied;
48
    for (int i = 1; i <= n; i++)
49
    {
50
        if (times[i] && !die[i])
51
        {
52
            sum = 0;
53
            All_NoDied = 0;
54
            for (int j = i; !die[j]; j = a[j])
55
            {
56
                die[j] = 1;
57
                sum++;
58
                All_NoDied |= nodie[j];
59
            }
60
            if (!All_NoDied && sum > 1)
61
                Max++;
62
            Min += sum / 2;
63
        }
64
    }
65
    printf("%d %d\n", n - Min, n - Max);
66
}