自动搬运

查看原文

来自洛谷，原作者为

	laoliu12345 欲买桂花同载酒，终不似，少年游。||AFO

搬运于2025-08-24 22:19:51，当前版本为作者最后更新于2024-09-04 20:35:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P6342

解法说明

首先我们考虑一个点数为 $n$ 的环会产生多少价值，首先共有 $n \times (n-1) / 2$ 个，又由于是在环中，故对于每一个点对都可以找到两条不重合路径，所以环的价值就是上式。

而后我们考虑为了保持联通，相邻两个环间必须建一条边，但是由于左环到右环和右环到左环必须经过两次中间这条边，所以这条边不产生价值。

那么思路就很清晰了，每次找出小于等于 $k$ 的最大 $n \times (n-1) / 2$ 即可。

那就可以愉快的写代码了。

题目代码

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N=1e4,M=1e6+10;
int n,m,k;
struct node{
	int l,r;
}e[M];
int idx;
int lb(int k)
{
	int l=0,r=N,mid,ans=0;
    while(l<=r) 
	{
        int mid=(l+r)>>1;
        if(k>=mid*(mid-1)/2) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>k;
	while(k)
	{
		n++,idx++;
		int t=lb(k);
		k-=t*(t-1)/2;
		e[idx].l=n,e[idx].r=n+t-1;
		n=n+t-1;
	}
	cout<<n<<" "<<n+idx-1<<endl;
	for(int i=1;i<=idx;i++)
	{
		for(int j=e[i].l;j<e[i].r;j++)
		    cout<<j<<" "<<j+1<<endl;
		cout<<e[i].r<<" "<<e[i].l<<endl;
		if(i>1) cout<<e[i].l<<" "<<e[i-1].r<<endl;
	}
	return 0;
}