牛客网暑期ACM多校训练营（第二场）I 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 长度的方格正方形图，其中有 M 个陷阱；

让你在 图的边缘 的 小方格上 放置小车，使小车 安全通过 对面边缘 

（小车只会直行，而且两小车同时相遇于一个小方格时 两小车则会撞毁。速度相同 小车不会产生追尾事故）

问 最多可以放置多少辆车？

思路：通过图形模拟

n为偶数时 总数ans=2*n；

n为奇数时 总数ans=2*n-1；

当我们把车的方向转变一下时 就会发现问题简单了很多

思路：

         当n为偶数时 我们只需要分别标记 x y 这条路上是否已经有了陷阱 如果没有 ans则-1；

         奇数时 中间那一辆车有两条路可以走
         所以当中间 x y 那两条路都死了 其实才损失了一辆车
         但前面因为那两条路ans已经-2了 所以现在要ans+1

代码：

#include<bits/stdc++.h>
using namespace std;
const int  M=100010;
int main()
{
  int i,j,n,m;

  while(cin>>n>>m)
  {
    bool  x[M],y[M];//标记x y 每条路是否已经有陷阱 避免重复计数
    for(i=1; i<=n; i++)
      x[i]=y[i]=0;//初始化 x y

    int ans;
    int mix=0,miy=0;
    if(!n&1)//偶数 总方法数 ans=2*n
      ans =(n<<1);
    else ans=(n<<1)-1,mix=miy=(n>>1)+1;// 奇数 ans=2*n-1  中位数x y

    while(m--)
    {
      int l,r;
      cin>>l>>r;
      if(!x[l]) ans--;//x 少一条路
      if(!y[r]) ans--;//y 少一条路
      x[l]=y[r]=1;
      if(ans<=0)
      {
        ans=0;
        break;
      }
    }//因为奇数时 中间那一辆车有两条路可以走
    //所以当中间那两条路都死了 其实才损失了一辆车
    //但前面因为那两条路ans已经-2了 所以现在要ans+1
    if(mix&&x[mix]&&y[mix]&&ans>0) ans+=1; //减多了1  补上1

    printf("%d\n",ans) ;

  }
}