题目就是要求将要求的区域连通的最小代价，并且连接只能建立在相邻两个点之间。
先不管环，只考虑一条线的情况，这个时候可以用栈来处理，有点类似于括号匹配，只不过是这个括号是一定匹配成功的。开一个数组b[]，对于每一个区间[st, ed]，++b[st]，–b[ed]。之后，再开一个sum变量记录当前栈的深度，把b数组从前到后扫描一遍，并且sum += b[i]。如果sum > 0说明这一个点有被覆盖，因此答案+1；如果ans == 0说明不被覆盖，不要管它；另外，根据我们给出的都是匹配的括号，所以ans不可能小于0。
接下来断环成链，枚举从i点断开，那么对于一个区间[st, ed]，如果st或者ed比i小，那么就加上n（跑到了另一边），注意这个时候新的st可能比新的ed大，因此有必要判断+交换st ed。
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
int n, m, a[10000][2], b[2000], ans(0x3FFFFFFF);
int main()
{
scanf("%d %d", &n, &m);
for (int i = 0; i < m; ++i)
{
scanf("%d %d", &a[i][0], &a[i][1]);
--a[i][0], --a[i][1];
}
for (int i = 0; i < n; ++i)
{
memset(b, 0, sizeof(b));
int count = 0;
for (int j = 0; j < m; ++j)
{
int st = a[j][0] >= i ? a[j][0] : a[j][0]+n;
int ed = a[j][1] >= i ? a[j][1] : a[j][1]+n;
if (st > ed)
std::swap(st, ed);
++b[st], --b[ed];
}
for (int j = 0, sum = 0; j < n; ++j)
{
sum += b[i+j];
if (sum > 0)
++count;
}
ans = std::min(ans, count);
}
printf("%d", ans);
}
|
