304 字
2 分钟
[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
我也不会啊
贴代码
#include <cstdio>#include <cstring>#include <queue>using namespace std;int a[1000005], Maxn, t, Min, Max;int times[1000005];bool die[1000005], nodie[1000005];int Q[1000005];int main(){ //freopen("maf.in", "r", stdin); //freopen("maf.out", "w", stdout); int n; scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); times[a[i]]++; } //Q.resize(1000001); for (int i = 1; i <= n; i++) { if (!times[i]) { Max++; Q[++Min] = i; } } //printf("%d\n",Max);
//for (vector<int>::iterator it = Q.begin(); it != Q.end(); it++) for (int i = 1; i <= Min; i++) { //printf("%d---------%d=======\n",it-Q.begin(),*it); int k = a[Q[i]]; if (die[k]) continue; die[k] = 1; nodie[a[k]] = 1; --times[a[k]]; if (!times[a[k]]) { Q[++Min]=a[k]; } } int sum; bool All_NoDied; for (int i = 1; i <= n; i++) { if (times[i] && !die[i]) { sum = 0; All_NoDied = 0; for (int j = i; !die[j]; j = a[j]) { die[j] = 1; sum++; All_NoDied |= nodie[j]; } if (!All_NoDied && sum > 1) Max++; Min += sum / 2; } } printf("%d %d\n", n - Min, n - Max);}
[BZOJ 1124][POI 2008] 枪战 Maf
https://www.nekomio.com/posts/63/