UOJ283 直径拆除鸡

本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

本文作者：ljh2000 
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！

题目链接：http://uoj.ac/problem/283

正解：枚举+数学

解题报告：

　　这道题很神啊，我在考场上想了一下，觉得菊花树很正确，但是想想就会发现菊花树的答案稳定在2*n-1上，并不优秀。

　　题解说的很明白了，我们先枚举链的条数，计算出最优值，只需在算出的最优链数上连边即可。

　　有一些小trick，需要注意。

　　题解：http://vfleaking.blog.uoj.ac/blog/2292

　　

//It is made by ljh2000

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <complex>

using namespace std;

typedef long long LL;

int n,m,now,tot;

int ans,chain,last;

inline int getint(){

    int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();

    if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;

}

inline void work(){

	n=getint(); m=getint();

	for(int i=1;(i+1)*(i+1)<=n;i++) {//枚举链的条数

		now=0; tot=n;

		for(int j=i;j>=1;j--)

			now+=tot,tot-=2*j+1;

		now+=tot;

		if(now>ans) ans=now,chain=i;

	}

	tot=0; last=0;

	for(int i=chain;i>=1;i--) {//连边

		for(int j=1;j<=2*i;j++)

			printf("%d %d\n",tot+j,tot+j+1);

		if(tot>0) printf("%d %d\n",last,tot+i+1);

		last=tot+i+1; tot+=i*2+1;

	}

	if(chain==0) last=1,tot=1;

	while(tot<n) { tot++; printf("%d %d\n",last,tot); }

}

int main()

{

    work();

    return 0;

}