CF1138B
[TOC]
中文题意
给出N(保证是偶数)个人的资料,其中c[i]为1表示此人可以扮演小丑,a[i]为1表示此人可以扮演艺术家,然后让你把这群人分成两组.
有三点要求
- 两组人数必须相等.
- 第一组的小丑数量必须等于第二组的艺术家数量
- 一个人只能被分在一个组里面
输入
第一行给出N(2<=n<=5000)
随后一行给出N个数字,数字只会是01中的一个,第i个数表示c[i]
随后一行给出N个数字,数字只会是01中的一个,第i个数表示a[i]
输出
输出在第一场中出现的演员的编号(不限顺序,且若有多种方案,输出任意一种即可),以空格分隔
解析
题意非常简单明了.我们不难想到把人可以分为4种
我们用a,b,c,d来表示这四种人的总数量(在代码中使用了cnt1,cnt2….)
用a1,b1,c1,d1表示在第一场中出现的某种类的数量
用a2,b2,c2,d2表示在第二场中出现的某种类的数量
我们能得到两个恒等式
a1+b1+c1+d1 =n/2
a1+b1+2*c1 = a+c
我们有四个未知数,有两个方程,如果根据情况讨论的话情况太过复杂,所以我们考虑数据范围并不大,故采用暴力枚举的方式来解此方程组,我们只需要穷举b1,c1的取值,就能通过方程2解出a1,然后将这三个数带入方程1,就能解出来d1,如果a1,d1都合法,则得到了方程的解,然后再输出编号即可.
若无解则输出-1.
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <unordered_set>
#define ll long long
using namespace std;
void ioInit() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
struct Peo {
char c;
char a;
} peo[5100];
int cnt1 = 0, cnt2 = 0, cnt3 = 0, cnt4 = 0;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i) { // 注意此处的输入方式,切忌使用整型直接输入
cin >> peo[i].c;
}
for (int i = 0; i < n; ++i) {
cin >> peo[i].a;
}
for (int i = 0; i < n; ++i) {
if (peo[i].c == '0' && peo[i].a == '0') {
++cnt1;
} else if (peo[i].c == '0' && peo[i].a == '1') {
++cnt2;
} else if (peo[i].c == '1' && peo[i].a == '0') {
++cnt3;
} else {
++cnt4;
}
}
// cout << cnt1 << cnt2 << cnt3 << cnt4 << endl;
for (int b1 = 0; b1 <= cnt3; ++b1) {
for (int c1 = 0; c1 <= cnt4; ++c1) {
if (b1 + c1 > n / 2)
continue;
int a1 = cnt4 + cnt2 - b1 - 2 * c1;
if (a1 < 0 || a1 > cnt2)
continue;
int d1 = n / 2 - a1 - b1 - c1;
if (d1 < 0 || d1 > cnt1)
continue;
for (int i = 0; i < n; ++i) {
if (d1 && peo[i].c == '0' && peo[i].a == '0') {
--d1;
cout << i + 1 << " ";
} else if (a1 && peo[i].c == '0' && peo[i].a == '1') {
--a1;
cout << i + 1 << " ";
} else if (b1 && peo[i].c == '1' && peo[i].a == '0') {
--b1;
cout << i + 1 << " ";
} else if (c1 && peo[i].c == '1' && peo[i].a == '1') {
--c1;
cout << i + 1 << " ";
}
}
cout << endl;
return 0;
}
}
cout << "-1" << endl;
return 0;
}
总结
这种数学暴力的方式实在是让我没想到,一直在各种分情况讨论,看来面对数学问题应当多多注意其数据范围,适当使用暴力能够方便解题.
