描述
题解
这个题用贪心搞了一发,想着将所有点都放在 A 集合或者
2017.10.9 更新
本来这个题水过去了,结果没想到昨天下午出去一趟回来发现重判了, WA 了,贪心果然没法解,还是要最小割才行啊。
最小割实在是有些头疼,这是官方题解。
代码
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
int n, m, ans = 0;
template <class T>
inline void scan_d(T &ret)
{
char c;
ret = 0;
while ((c = getchar()) < '0' || c > '9');
while (c >= '0' && c <= '9')
{
ret = ret * 10 + (c - '0'), c = getchar();
}
}
int main()
{
scanf("%d%d", &n, &m);
// 全放 A 集合
int x, y;
for (int i = 1; i <= m; i++)
{
scan_d(x);
scan_d(y);
ans += abs(x - y);
}
// 全放 B 集合
int sum = 0;
for (int i = 1; i <= n; i++)
{
for (int j = i + 1; j <= n; j++)
{
sum += j - i;
}
}
ans = max(ans, sum - ans);
printf("%d\n", ans);
return 0;
}