贪心 CF 333B Chips - c++编程基础

TOP

贪心 CF 333B Chips

2014-11-23 21:42:16 来源: 作者: 【大中小】浏览:11次

Tags：贪心 333B Chips

题目意思：

给一个n*n的矩阵，里面有m个障碍点，问最多可以在不是角落的边框上放多少个点，使得所有点的同时向对面移动，不遇到障碍点且不相互冲突。

解题思路：

贪心思想。

首先障碍点所在行和列不能放，然后当n为奇数时，n/2+1行和列只能放一个，其他行或列只要能放就放，因为不冲突，对于任意一行和一列，四种情况中必有一种满足他们两之间不冲突。

代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/

bool row[1100],col[1100];

int main()
{
   int n,m;

   while(~scanf("%d%d",&n,&m))
   {
      memset(row,false,sizeof(row));
      memset(col,false,sizeof(col));

      int a,b;
      for(int i=1;i<=m;i++)
      {
         scanf("%d%d",&a,&b);
         row[a]=true;  //障碍点所在行和列不能放
         col[b]=true;
      }
      int ans=0;

      for(int i=2;i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：HDU 3333 树状数组+离线处理	下一篇：栈的数组实现

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: