牛客网暑期ACM多校训练营（第二场）car

链接：https://www.nowcoder.com/acm/contest/140/I
来源：牛客网
 

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

White Cloud has a square of n*n from (1,1) to (n,n).
White Rabbit wants to put in several cars. Each car will start moving at the same time and move from one side of one row or one line to the other. All cars have the same speed. If two cars arrive at the same time and the same position in a grid or meet in a straight line, both cars will be damaged.
White Cloud will destroy the square m times. In each step White Cloud will destroy one grid of the square(It will break all m grids before cars start).Any car will break when it enters a damaged grid.

White Rabbit wants to know the maximum number of cars that can be put into to ensure that there is a way that allows all cars to perform their entire journey without damage.

(update: all cars should start at the edge of the square and go towards another side, cars which start at the corner can choose either of the two directions)

 

For example, in a 5*5 square

 

legal

 

illegal（These two cars will collide at (4,4)）

 

illegal (One car will go into a damaged grid)

输入描述:

The first line of input contains two integers n and m(n <= 100000,m <= 100000)
For the next m lines,each line contains two integers x,y(1 <= x,y <= n), denoting the grid which is damaged by White Cloud.

输出描述:

Print a number,denoting the maximum number of cars White Rabbit can put into.

示例1

输入

复制

2 0

输出

复制

4

备注:

题意：在一个n*n的方格里，我们要在每条边上摆放小车，然后小车向另一边移动，当两个小车相遇在同一个格子里或者走到事先被标记的点的话就会毁掉，问最多可以摆放几个小车

思路：这个按照题目里的画法画一画就会发现如果n为偶数，最多放2*n个，奇数时2*n-1个，然后我们统计被破坏的行和列，若这一行有标记点则减一，列同理，但是要注意当n为奇数时，他的中间那一行或者列最多只能放一个小车，所以按照算法的统计，当n为奇数时，若中心点被标记，要加一，否则会与结果不符；

下面附上我的代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#define LL long long
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define lson o<<1
#define rson o<<1|1
using namespace std;
int n, m;
int a[100005], b[100005];
int main()
{
	int x, y;
	while(cin >> n >> m)
	{
		memset(a, 0, sizeof(a));
		memset(b, 0, sizeof(b));
		int sum, x, y;
		if(n % 2)
			sum = 2 * n -1;
		else
			sum = 2 * n;
		while(m--)
		{
			scanf("%d %d", &x, &y);
			a[x] = 1;
			b[y] = 1;
		}
		for(int i = 1; i <= n; i++)
		{
			if(a[i])
				sum--;	
			if(b[i])
				sum--;
		}
		if(n % 2 && a[n / 2 + 1] == 1 && b[n / 2 + 1] == 1)
				sum++;
		printf("%d\n", sum);
	}
    return 0;
}