Codeforces 1173B Nauuo and Chess（greedy）-蒲公英云

Codeforces 1173B Nauuo and Chess（greedy）

B.Nauuo and Chess

题意：棋盘是一个正方形，让你放n个旗子满足 |ri−rj|+|ci−cj|≥|i−j|. 问你棋盘最小多大。

题解：贪心。
从第一个开始放，满足公式，让1-n旗子紧挨着，从（1，1）开始，然后先让n/2+1前的棋子纵坐标相同，后面的棋子横坐标相同，这样好看，你看纵坐标相同的棋子紧挨着所以他们|i-j|只差1，他们的坐标差纵坐标相同，横坐标只差一；横坐标相同的同理，不挨着的棋子也会满足公式，因为你是从第一个贪心过来的，把不相邻的一直往前推，总会碰到的。
所以最小棋盘边长为n/2+1。棋子摆放为正方形的相邻两边。
AC代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int mmax=1e6+10;
const int eps=1e-8;
ll a[mmax],b[mmax];
int main()
{
    ll a;
    while(cin>>a)
    {
        cout<<a/2+1<<endl;
        for(int i=1;i<a/2+1;i++)
            cout<<i<<" "<<"1"<<endl;
        for(int i=a/2+1,j=1;i<=a;i++,j++)
            cout<<a/2+1<<" "<<j<<endl; 
    }
    return 0;
}