题面
大秦为你打开题目传送门
题目描述
今年高考后，老师在班上做了一个关于学生成绩的调查。这个班有 $n$ 个学生，从 $1$ 到 $n$ 进行编号。学生们不想告诉老师他们的确切分数，只告诉老师他们在省里的排名。
老师问了所有的学生之后，发现有些学生没有说实话。例如，学生 $1$ 说他在 $5004$ 到 $5005$ 之间，学生 $2$ 说他在 $5005$ 到 $5006$ 之间，学生 $3$ 说他在 $5004$ 到 $5006$ 之间，学生 $4$ 说他也在 $5004$ 到 $5006$ 之间。这种情况显然是不可能的。所以至少有一个人说了谎。
因为老师认为他的学生大多数是诚实的，他想知道最多可能有多少学生说真话。若有多解，输出字典序最大的。
思路
首先这是一眼最大匹配，但是如何做到字典序最大呢？因为匈牙利算法的特性，我们直接从 $n$ ~ $1$ 去增广求最大匹配就好了。
代码
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
86
| #pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 100010;
int n, m;
pair<int , int >a[110];
int ma[N];
int flag[110];
int vis[N];
inline void Input() {
read(n);
for(int i = 1; i <= n; i++) {
read(a[i].first, a[i].second);
}
}
inline bool Dfs(int u) {
for(int i = a[u].first; i <= a[u].second; i++) {
if(!vis[i]) {
vis[i] = 1;
if(!ma[i] || Dfs(ma[i])) {
ma[i] = u;
flag[u] = 1;
return 1;
}
}
}
return 0;
}
inline void Work() {
int ans = 0;
for(int i = n; i >= 1; i--) {
memset(vis, 0, sizeof(vis));
if(Dfs(i)) ans++;
}
printf("%d\n", ans);
for(int i = 1; i <= n; i++) {
if(flag[i] == 1) {
printf("%d ", i);
}
}
}
int main() {
int T = 1;
while(T--) {
Input();
Work();
}
return 0;
}
|
