4288120_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <algorithm>

using namespace std;

int n, p;

struct node
{
	int a, b;

	bool operator < (const node &t)	const
	{
		if (a == t.a)
		{
			return b < t.b;
		}
		return a < t.a;
	}
}c[1000], q[1000];

int main()
{
	int i, j;

	scanf("%d%d", &n, &p);
	for (i = 0; i < p; i++)
	{
		scanf("%d%d", &c[i].a, &c[i].b);
		c[i].a--;
		c[i].b--;
		if (c[i].a > c[i].b)
		{
			swap(c[i].a, c[i].b);
		}
	}
	int ans = -1;
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < p; j++)
		{
			int a = c[j].a;
			int b = c[j].b;
			a += i;
			b += i;
			q[j].a = a;
			q[j].b = b;
		}
		sort(q, q + p);
		int tmp = 0;
		for (j = 0; j < p; j++)
		{
			int k = j + 1;
			int max = q[j].b;
			while (k < p && q[k].a <= max)
			{
				if (q[k].b > max)
				{
					max = q[k].b;
				}
				k++;
			}
			tmp += max - q[j].a;
			j = k - 1;
		}
		if (ans == -1 || tmp < ans)
		{
			ans = tmp;
		}
	}
	printf("%d\n", ans);
	return 0;
}