思路

我们先看什么时候可以最大构造，设 $n$ 个点平铺在 $a\times b$ 的平面上，那么曼哈顿距离为1的点对有 $a(a-1)+b(b-1)$ 对，考虑其最大值:

\begin{aligned} a(a-1)+b(b-1)&=a^2+b^2-(a+b) \\ &\ge 2ab-2\sqrt{ab} \ , \ \text{with equality iff } a=b=\sqrt n \end{aligned}

但是这里是整数向下取整得 $k<=2n-2 \lfloor \sqrt n \rfloor$ 时是有解的，同时也说明了点聚集地越似正方形，点对的贡献值越大。那么我们考虑先贪心地选择正方形，如何构造这样紧密的点集呢？

不难发现有个蛇形路径可以满足我们的需求：

17 18 19  20 21
16  5  6  7  22
15  4  1  8  23
14  3  2  9  24
13 12 11 10  25
      28 27  26

这里面的数字代表点的序号，按照此次序摆放的点最紧密。如此摆放的点集每次对贡献增加最多2，最少1，也就是存在总体的贡献 $s:=x+2y$ 那么如果增加的贡献为2导致大于k，此时直接在整体的最右侧加个点就行了。

如果剩下还有点，那就找个远点的地方别挨着放。

代码

这里说明下如何构造这个蛇形点列，枚举几个环就会发现第 $l$ 环的点数总是 $8\times l$ ，那么每个环有四个边，每个边有 $2l$ 个点，如此遍历就很容易构造了。

以及使用set来查找相邻点 ~~实际上用二维数组也可以，但我没试过会不会MLE~~

const int dx[]={0,0,-1,1};
const int dy[]={-1,1,0,0};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k; cin >> n >> k;
	if(k>2*n-2*sqrt(n))return cout << "No",0;

	vector<pii> a,ans;
	set<pii> st;
	
	int sx=0, sy=0;
	a.push_back({sx,sy});
	for(int l=1; l<=1e3; l++)
	{
		a.push_back({sx,--sy});
		for(int tx=0; tx<2*l-1; tx++)a.push_back({--sx,sy});
		for(int ty=0; ty<2*l; ty++)a.push_back({sx,++sy});
		for(int tx=0; tx<2*l; tx++)a.push_back({++sx,sy});
		for(int ty=0; ty<2*l; ty++)a.push_back({sx,--sy});
	}
	
	int p=0, fx=2e6;
	int s=0;
	while(ans.size()<n)
	{
		if(s==k)
		{
			ans.push_back({fx,fx});
			fx+=2;
			continue;
		}
		auto [x,y]=a[p++];
		int cnt=0;
		for(int i=0; i<4; i++)
		{
			int nx=x+dx[i], ny=y+dy[i];
			if(st.count({nx, ny}))cnt++;
		}
		if(cnt+s<=k)
		{
			s+=cnt;
			ans.push_back({x,y});
			st.insert({x,y});
		}
		else
		{
			int mx=INT_MIN, my=0;
			for(auto &[xx,yy]:st)if(xx>mx)
				mx=xx, my=yy;
			s+=1;
			st.insert({mx+1,my});
			ans.push_back({mx+1,my});
		}
	}
	cout << "Yes\n";
	for(auto &[x,y]:ans)cout << x << " " << y << endl;
	


	return 0;
}

题解 | #小红的点构造#

思路

代码